哈希表（Hash Tabel）

这是无量测试之道的第163篇原创

面试的时候，曾被问过：你知道字典的底层数据结构是什么吗？

  那我们今天主要讲的就是哈希表这种数据结构到底是什么样子的；哈希碰撞是怎么造成的以及是如何解决哈希碰撞的。

1.定义

  哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做哈希表。

  字典存值案例如下代码。为了能比较通俗的理解哈希表这种数据结构，我们先看下图:

    put("jack","666")
    put("Rose","777")
    put("Evan","888")

复制

  Hash Table主要由2部分组成：

1. 哈希函数
2. Table 「 底层是一个数组，一般数组大小是2n 」至于为什么是这样，是为了位运算的方便

Hash函数和Table的作用

  hash函数的主要作用是将key进行操作，生成一个整数的索引值index。对应我们的案例：

• hash("Jack") --> index = 14
• hash("Rose") --> index = 01
• hash("Evan") --> index = 03

  然后根据index将对应的value存储到Table数组中。从而完成key和value的映射。

2.Hash碰撞

  我们往字典里面再加入一组数据(Jeffery,999)，假设hash("Jeffery") --> index = 03,此时就会发现，Jeffery和Rose的index都为3，冲突了，这就是Hash碰撞。

3.解决Hash碰撞

  解决Hash冲突的常见方法：

• 1. 开放定址法(Open Addressing)：按照一定规则向其他地址探测，直到遇见空的位置
• 2. 再哈希法(Rr-Hashing)“设计多个hash函数
• 3. 链地址法(Separate Chaining)比如通过链表将同一index的元素串起来

  今天主要要介绍的是链地址法，当发现hash碰撞的时候，可以使用单链表将同一index的元素串起来，如下图所示：

4.如何生存key的哈希值？

  key常见的种类可能有：整数、浮点数、字符串、定义对象。   不同种类的key，哈希值的生成方式不一样，但是目标是一致的：

• 1. 尽量让每个key的哈希值是唯一的
• 2. 尽量让key的所有信息参与运算

  本文的key都为字符串，以jack为例：jack的哈希值可以表示为：j * n^3 + a * n^2 + c * n^1 + k * n^0jack的ASCII都是可查的，所以通过上述计算可以得到一个整数T，然后通过与Table数组的大小进行&位运算或者%去余运算，就可以得到inedx下标值。

  关于整数、浮点数、定义对象的哈希值的计算方式，大家感兴趣的话可以去搜索一下，有比较系统的讲解。

总结

  今天主要介绍了哈希表这种数据结构到底是怎样存值的，紧接着讲解了哈希碰撞是怎么产生的以及是如何解决的，最后介绍了字符串key的的哈希值的计算方式。相信大家认真看完本文，对哈希表到底是什么有了一个比较清晰的认识。