1.5 散列表

散列表也叫作哈希表，是根据键值对（key,value）进行存储的一种数据结构。它把一对（key,value）通过key的哈希值来映射到数组中，也就是说，它通过把关键值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数叫作散列函数，存放记录的数组叫作散列表。

举个例子，为了查找某个好友的微信号，可以按照好友首字母顺序查找，在首字母为W的表中查找王姓的好友，显然比直接查找要快得多。这里使用人名作为关键字，取首字母是这个例子中散列函数的函数法则，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

1. 冲突处理

由于关键字的函数映射关系，散列表难免会出现哈希冲突，也就是不同的key值通过散列函数，可以映射到一个数组中的同一个位置，这就是哈希冲突。哈希冲突不一定是哈希值冲突，也有可能是函数映射的结果出现冲突。比如一个哈希值是654321，另一个哈希值是978321，而哈希函数是取它们的后3位，所以它们通过哈希函数计算的结果都是321。

2. HashMap

关于散列表大家最熟悉的可能就是HashMap了，HashMap实际上是数组加链表的一种数据结构，当出现哈希冲突的时候，它会以链表的形式存在，如图1-20所示。

HashMap的哈希映射函数非常简单，就是用数组的长度减1，然后和哈希值进行与运算，（n-1）&hash，这里n是数组的长度，也是2的幂次方。这个运算非常巧妙，我们来介绍一下它是怎样把一个数变成不小于它的2的幂次方的。比如传入17会返回32，传入32也会返回32，传入33会返回64，它返回的都是2的幂次方，并且不能小于传入的值。第一种方式通过while循环，这种方式比较简单。

第二种方式相当于把一个数的二进制中最左边的1往右铺开，最后加上1就变成不小于它的2的幂次方，如图1-21所示。这里在最开始的时候减1，是为了防止本来就是2的幂次方，通过运算会放大一倍，比如32，在开始运算的时候如果不减1，最后就会变成64。i必需是正整数。

第三种方式，首先判断如果本来就是2的幂次方，直接返回，2的幂次方在二进制中只有一个1，其他位都是0。否则也是把最左边的1往右边铺开，然后只保留最左边的1，其他的都减掉，最后往左移一步就行了。

3. ArrayMap

除了HashMap以外，还有一个类是ArrayMap，它是一种纯数组的数据结构，由两个数组构成，一个存放哈希值，另一个存放key和value，其中存放key和value的数组长度是存放哈希值数组长度的2倍，并且存放哈希值的数组是有序的，查找的时候是通过二分法进行查找。当出现哈希冲突的时候，说明哈希值是一样的，它们在哈希数组中是挨着的，查找的时候如果有相同的哈希值，但key值不一样，我们还需要往两边进行查找，如图1-22所示。

4. SparseArray

还有一个和ArrayMap非常相似的数据结构，它就是SparseArray，SparseArray也有两个数组，和ArrayMap不同的是这两个数组长度都是一样的，一个数组存放的是key值，另一个数组存放的是value值，大家可能会有疑惑，怎么没有存放哈希值的，其实这里的key值可以把它看作是哈希值，因为这里的key值必须是int类型，并且存放key值的数组也是有序的，查找的时候也是通过二分法进行查找，如图1-23所示。