Each data structure has it's own time complexities.  The biggest one that jumps out at you is the hash table.  The average times for Insertion, Deletion and Searching are all O(1).  But it's really just constant time, since there can be multiple reps through each of these to find the right spot.  The real question is, can we do each of those operations in exactly one operation, if space wasn't an issue?Recently I was working on the radix sort, and figuring out how to speed it up as much as possible.  The one thing I settled on was doing a 2-byte counting sort, thus you would only have to loop once through.  Then I got to thinking about the trie I used before, with integers where I traversed through by modding the number by 10 each time through.  This seemed to be faster than any other data structure that I've tried, but wanted to make it faster.  What I tried today was treating the trie as a guaranteed 2-level tree.  Each node with 2^16 (65536) children.  That way I can reference each number like this: root->link[twoByte1]->link[twoByte2].  Where twoByte1 is the first 16 bits, and 2 is he 2nd.  Problem is, this is a lot of memory.  Instead I decided to make an array of structures, with 2^16 bool (uint8_t) values instead, and ran across the same issue.  To fix this, I made the following structure.struct trie {    unsigned int link[2048];};I decided to use 2048 unsigned integers (or signed, wasn't sure if there would be a difference) instead.  That way I can treat each bit as the true/false value during look up.  In order to reference each position, I would take the first 16 bytes, and reference the element he same way as before, but the 2nd I would divide by 32 to find out which element of the integer array to use, and mod the number again by 32 to find out which bit to look at.  The following is the code I used to reference it:uint8_t getData (int data, uint16_t& dir, uint16_t& pos, uint8_t& x) {    dir = (data >> 0)  & 0xffff;    pos = (data >> 16) & 0xffff;    x   =  pos / 32;    return pos % 32;}The insert function was simply finding the spot and turning the bit on.  To do this, I would get the data from the function above, then OR the specific bit with 1.  Similarly with deletion, only I would invert the bit string, then AND it, to turn it off.  Then to search for that element, I would just return the specific bit.  Help with how to clear the bit was found here: https://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c   Below is the code for those three functions.void insert(trie *root, int data) {    uint16_t dir, pos;    uint8_t x, y = getData(data, dir, pos, x);    root[dir].link[x] |= 1 << y;}bool find(trie *root, int data) {    uint16_t dir, pos;    uint8_t x, y = getData(data, dir, pos, x);    return root[dir].link[x] & (1 << y);}void remove(trie *root, int data) {    uint16_t dir, pos;    uint8_t x, y = getData(data, dir, pos, x);    root[dir].link[x] &= ~(1 << y);}From here it was as simple as initializing the array of structs.  The great thing is that with the number of elements coming in, the data structure will never grow any farther out.  Also, in the case of threading, since I'm only turning the bits on during insertion, I don't think I would need to synchronize any of the threads.  Therefor it could be speed up with threading.  What are your thoughts on this, I did a test case here: http://ideone.com/McwWTV .  I ran a test on a Linux machine running on an i7, and was able to process 250 million integers per every 2.5 seconds.
Fast integer handling
c++;algorithm;performance;binary search;hash table