Hash Function for Trie based implementation

Question

I am supposed to build a dictionary Trie and use Nodes. I need to store them in a hashtable. I need to create a Hash Function to place the nodes in the correct location. How can i convert the String to an integer in the Hash Function?

Answer 1

You can try a kart-trie. It uses a clever key-alternating algorithm to hide a trie-data structure in a binary tree:http://code.dogmap.org/kart/.

The translated bit at position pos in a key k of length klen can be calculated as:

unsigned int bit(size_t pos, unsigned char const* k, size_t klen) { if (pos/(CHAR_BIT+1)>=klen) return 0; if (pos%(CHAR_BIT+1)==0) return 1; return (((unsigned int)k[pos/(CHAR_BIT+1)])>>(CHAR_BIT-pos%(CHAR_BIT+1)))&(unsigned int)1; }

Answer 2

A common hash example, while not necessarily a good one, is to take sum of the ascii values of each character in the string, modulo the size of the hash table.