Hash Table 哈希表 C++ 例子
What's a Hash Table? Why we need a Hash Table?
By Using a Hash Table we can find element very quickly. For example, There are 20 random number in an array below.
It's not a sorted array, So We can not use Binary Search to finding a number, When we need to find 118, We need 12 comparisons! Finding number like 270, 198, we need even more comparison.
We change the way the 20 number store. We store them in 10 linked lists. There is a rule, If the number's last digit is 0, so we insert it in a linked list which index is 0. Look at the Figure 1 for more detail. like number 118, it's last digit is 8, so we insert it in ninth linked list.
So in this way, We find 118 only need 1 comparison in the ninth linked list! Finding number like 270 or 198, we need just 2 comparisons.
Note that the basic hash table which we explained above used a modulo function. There are many way to hash data, but modulo is the most common. What's more, the modulo function often use a prime number. That was because you get fewer collisions when you modulo a key by a prime number. Having fewer collisions makes your table easier to work and more efficient. There is a completed mathmatical reasoning behind this, but it is okay for us to assume that this is true for us.
You need have some STD knowledge, We will use "list" in STD instead of using customied linked list. And we also use "find" and "erase" function.
A more completed Hash Table class
http://www.waitingfy.com/?p=480
