[数据结构]哈希表

什么是哈希表
首先说说什么是表？顾名思义，就是通过提供的key随机访问到value。那么哈希表，就是通过哈希的方式来实现表。什么叫哈希？哈希又叫散列，就是把任意长度的输入通过哈希函数转化成固定长度的输出，而这个输出就是哈希值。

哈希表种类和实现
哈希表一般分为两种：链式哈希表，开地址哈希表。
链表哈希表，一般是每个任意长度的输入通过哈希函数转化成固定长度的输出，然后放到桶（Bucket）里。如果出现不同的输入产生同样的哈希值就碰撞了，碰撞了就追加到桶里，碰撞的越多，桶就越满。
开地址哈希表，一般是每个任意长度的输入通过哈希函数转化成固定长度的输出，放到哈希值对应的slot里，如果冲突了就继续哈希（另外一种哈希方法），直到找到一个空的slot为止。

哈希表的用途
一般随机访问的都可以使用哈希表来实现。最为我们熟知的用法，可能就是编译是产生的symbol table了。