常识

1.1.哈希表 (hash tables)

• 哈希表（也叫散列表），根据键值对(Key-value)而直接进行访问的数据结构。
• 它通过把key和value映射到表中一个位置来访问记录，这种查询速度非常快，更新也快。
• 而这个映射函数叫做哈希函数，存放值的数组叫做哈希表。
• 通过把每个对象的关键字k作为自变量，通过一个哈希函数h(k)，将k映射到下标h(k)处，并将此对象存储在这个位置。

1.2.具体操作过程

• 1.数据添加：
  • 把key通过哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余
  • 取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
• 2.数据查询：再次使用哈希函数将key转换为对应的数组下标，并定位到数组的位置获取value。

1.3.解决hash冲突

• 链地址法
• 再哈希法
• 建立公共溢出区
• 开放定址法