哈希表概述

数组的优点是能够快速的查询

链表的优点是快速的插入和删除

将这数组和链表的有点结合到一起，就出现了哈希表。

哈希表由两个部分组成

hash函数：哈希表能否快速定位，很大程度就是取决于hash函数，hash函数的好坏决定了哈希表的性能。

hashTable：存放数组的表，就是hashtable。

不同的key，经过hash函数之后，寻址出来的位置可能是同一个，在hashtable的同一个位置，就是产生了冲突，JDK1.8之前解决冲突的办法是在数组的位置，放了一个链表，就是拉链法。JDK1.8之后，当链表的个数达到阈值之后，在当前的数组位置放了一个红黑树，红黑树的定位比链表更快。

装填因子：

它是hash函数和数组的大小，产生冲突的解决方案。因为数据越是接近数组的大小，越容易产生冲突，产生冲突就越多，装填因子可以自己进行设定，0.75 0.8都可以。

缺点：

扩容的时候，需要重新计算，重新hash计算每个节点，在新的hashtable中的位置。

应用：

微信通讯录，电话号码，QQ的好友数量都是有上限的。

什么样的哈希表是最好的？

没有冲突的哈希表最好，如果有冲突，每个数组下面的原数个数一样多。