什么是散列表
散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”。
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
Java中HashMap是如何实现的
1. 初始大小
HashMap 默认的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高 HashMap 的性能。
2. 装载因子和动态扩容
最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
3. 散列冲突解决方法
HashMap 底层采用链表来解决冲突。链表法是一种更加常用的散列冲突解决办法。如下图，在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
然而即使负载因子和散列函数设计得再合理，也免不了会出现链表过长的情况，一旦出现链表过长，对于查询数据的时候，会严重影响 HashMap 的性能。于是，在 JDK1.8 版本中，为了对 HashMap 做进一步优化，引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。
4. 散列函数
int hash(Object key) {
int h = key.hashCode()；
return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小
}
其中，hashCode() 返回的是 Java 对象的 hash code。
通过Java的HashMap的实现可以总结出散列表的实现规律：
散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。
