So wait... You have 64 bits keys and 32 bits values. Then why not store the values in the keys? Use the lower 32-bits for the value, and the higher 32 bits to c

So wait... You have 64 bits keys and 32 bits values. Then why not store the values in the keys? Use the lower 32-bits for the value, and the higher 32 bits to count how many duplicates you have. int32_t big_array[2^32] = {0}; /* returns the key */ int64_t write(int_32 value) { big_array[value]++; return big_array[value] << 32 & value; } /* returns the value */ int32_t read(int64_t key) { return (int32_t) key; } /* all indexes between 1 and the return value are valid higher half values for the key. The lower half is the value itself. */ int32_t seek(int32_t value) { return big_array[value]; } memory: 16GB access: O(1) seek: O(1) Problem solved! :) edit: I'm missing the "Use less memory than an array in all circumstances" requirement, but hey, you talk about "billion of records" in your post.