散列表

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

散列表理解

举个例子，100个参加比赛的跑步选手，依次从1-100编号，录入程序中。想要根据编号来找到选手信息，可以用编号作为key，选手信息作为value，找到key（数组下标），就找到了对应的选手信息。Java中的HashMap就是散列表。
上例的选手编号如果不是整数，就不能用选手编号作为数组下标去遍历数组。比如编号是a01-a100,那么就要取后两位。或者编号是乱序的，就要生成一套指定的对应规则映射到数组的key。比如前三个选手的编号分别是： aaa,aba,bba. 把选手信息放到数组里，通过编号获取选手信息。这时需要一个规则，把编号映射成数字（数组下标），然后把选手信息存进对应数字下标数组位置里。例如这里，a对应1，b对应2，那么这三个选手的下标分别是111,121,221,把他们的信息存到数组的这三个位置里。写成个函数 hash(key),返回值是整数，就可以用这个hash函数，把所有编号映射成数组下标，放到对应位置去。取选手信息的时候，获取选手的编号 bba,hash(bba),得到整数的数组下标，然后去数组里取得选手信息（散列值）。

散列函数（hash）基本要求

• 散列函数计算得到的散列值是一个非负整数；
• 如果 key1 = key2，那 hash(key1) == hash(key2 )；
• 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

散列冲突

在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。所以我们几乎无法找到一个完美的无冲突的散列函数，即便能找到，付出的时间成本、计算成本也是很大的，所以针对散列冲突问题，我们需要通过其他途径来解决。

散列冲突解决办法

1、开放寻址法
出现散列冲突以后，不同的两个key散列成了相同的值。比如上例中aaa和bbb选手经过某个hash函数都散列成了111，aaa先存，111位置是空的，把aaa存进去。bbb后存，发现111位置满了，开放寻址法就是，顺着数组往后查，看112位置有没有，112位置有了，继续往后找，直到找到一个空的位置，存进去。 取值的时候，hash(bbb)=111，去111找，取出来array[111]（注意此时选手信息中也有key，即编号），对比一下key，发现是aaa，不是bbb，接着往后。一直找，如果找到了，说明有。没找到，说明bbb不在散列表里。
2、链表法 （HashMap的解决办法）
在散列表中，每个位置都包含一个链表。

image.png

每次插入的时候，散列函数计算出对应的散列位置，然后如果有冲突，顺序放入链表里。查找的时候，散列算出散列位置（散列槽、桶），遍历链表即可。

思考

1、假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
10万条url访问记录，有些是重复的，重复的加起来是这个url的访问次数。

2、有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？