c++ - Is there a fastest way to count object repetitions in an array than a HashTable? -

i'll try clear can. have implemented solution , works, need know if best use other data structure instead of hash table

it's college question, submitted teacher , works, wanted see if have done differently.

so, problem:

given image ( ppm 3,all data stored ascii in rgb ) e.g.

p3 # p3 means colors in ascii, 3 columns , 2 rows, # 255 max color, rgb triplets 3 2 255 255   0   0     0 255   0     0   0 255 255 255   0   255 255 255     0   0   0 

i need divide each pixel constant given wich power of 2 ( 2,4,8…………64,128)

c= 32; pixel2(255/c,255/c,255/c) = pixel2(7,7,7) 

then, need convert pixels patches of given width,and patch accumulate rgb values of pixels contains

e.g.

w=3;   imagew = 10; imageh=10; patch[0].r = pixel[0].r + pixel[1].r + pixel[2].r +              pixel[10].r + pixel[11].r + pixel[12].r +              pixel[20].r + pixel[21].r + pixel[22].r; patch[0].g = same g component; patch[0].b = same b component;  patch[1].r = pixel[1].r + pixel[2].r + pixel[3].r +              pixel[11].r + pixel[12].r + pixel[13].r +              pixel[21].r + pixel[22].r + pixel[23].r; etc… 

then, need count number of repetitions of each patch in image. so, i've done it's have image class, reads image file (ifstream), , pixel class, has r,g,b , naparations components. read pixels, divide them tha constant given, , patches acumulating values of it's containing pixels.

after have data vector in image class wich it's array of patches objects e.g.

data = [patch0{r comp,g comp, b comp, 1 parition}, patch1{r comp,g comp, b comp, 1 parition} …..]; 

now, i've done it's using hash table, insert each patch, if it's inserted, update it's nappearances component, if not, insert it. after inserted, return vector elements in hash table. vector, have 1 ocurrence of each patch, , it's nappearances component cointain tha number of times each patch appears in image.

is there other way? or hash table best approach?

also, kind of hash function use? i'm using

hash = patch.r * 1 + patch.g *2 + patch.b*3; tablesize = maximun number of patches (assuming no 1 repeats) insert table[hash%tablesize]; 

the hash table allows collision, each position in table has list of elements.

sorry if it's large, wanted clear. sorry if english isn't enough! thanks.

2 things

first: if going hash colors:

if r, g , b colors 00 ff simplest thing create hash function 24-bit i.e. rrggbb mod prime number size of hash table. size hash-table? prime number?

for example 65536 poor choice of hash-table size. 65539 fine.

unsigned int colornum( unsigned int red, unsigned int green, unsigned int blue ) { return (red << 16 | green << 8 | blue); }

then hash colornum(r,g,b) % hashtablesize;

alternatives hash: use std::set rgb 24-bit number, or rgb numbers compare using 24-bit number. way can count number of duplicates. not fast hash though.

by way, if can afford it, 2^24 16m , if used bitset use 2mb. run through colors setting "flag" each color occurs count duplicates way.