哈希表是一种可以快速定位得数据结构。哈希表可以做到平均查找、插入、删除时间是O(1)，当然这是指不发生Hash碰撞得情况。而哈希表最大得缺陷就是哈希值得碰撞(collision)。
Hash碰撞：就是指hash桶有多个元素了。常见解决哈希碰撞得方法就是在hash桶后面加个链表
这里就引入第一个问题：为什么Map的底层设计要采用哈希表的这种数据结构？
HashMap设计时，要求其key不能重复。所以每次往HashMap设置值时，需要对HashMap现在容器所有key进行筛选，以保证不会对HashMap设置同样得key。
如果以普通if、else来判断得话，这样查找效率会非常得低。如果里面元素个数达到几百得话，程序得运行效率就会非常低。而这种情况，很符合哈希表得解决场景。
哈希表得一种实现方式就是数组+链表。这也是java7HashMap底层哈希表的实现方式。
二、JDK1.7的HashMap 1、相关概念（1）初始容量
/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16（2）负载因素
/** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f;（3）阙值
/** * The next size value at which to resize (capacity * load factor). * @serial */ // If table == EMPTY_TABLE then this is the initial capacity at which the // table will be created when inflated. int threshold;（4）hash种子
/** * A randomizing value associated with this instance that is applied to * hash code of keys to make hash collisions harder to find. If 0 then * alternative hashing is disabled. */ // 标志位，是jdk为了解决hashMap安全隐患做的补丁 transient int hashSeed = 0; 2、源码分析（1）put
public V put(K key, V value) { /* hashMap默认是延迟初始化，只有在用的时候，才会开辟空间 */ // 如果hash表为空，则开始扩容hash表 if (table == EMPTY_TABLE) { inflateTable(threshold); } // 对key为null的相关操作 if (key == null) return putForNullKey(value); // 计算key的hash值 int hash = hash(key); // 计算key的hash值对应哈希桶的下标 int i = indexFor(hash, table.length); // 对哈希桶内的链表进行更新操作：可以看到如果是第一次插入，返回的就是null for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } }（2）inflateTable：扩充哈希表
private void inflateTable(int toSize) { // Find a power of 2 >= toSize /* 这里会发现即使你输入hashMap容量不是2的n次方，这里也会强制变成2的n次方 */ // 计算哈希表桶的个数 int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; // 按需初始化hash种子，也是解决hashMap安全隐患做的补丁 initHashSeedAsNeeded(capacity); }（3）indexFor：计算key在哈希桶的下标
static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }这个方法就是为什么hashMap的初始值要设置2的n次方的原因。它可以快速得到key要放在hash桶的下标。
（4）扩容方法
当hashMap的size大于threshold时，就会扩容。而threshold = 容量 * 阈值
低效
线程不安全
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; // 将旧哈希表的元素转移到新的哈希表；这里是死锁的原因 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } 3、jdk1.7的HashMap中的缺点（1）死锁问题
死锁问题是因为用户将HashMap应用到多线程的环境下。详情参考：https://coolshell.cn/articles/9606.html
死锁问题是由于HashMap在扩容时，里面元素的顺序可能没有按照之前顺序排列，从而导致环形链表，造成死锁情况。
（2）潜在的安全隐患
tomcat底层接收参数是使用hashTable接收，假设黑客使用特意组合的参数，使用所有的参数都挂载在同一个哈希桶中。这就会使得哈希表退化成链表。这其实就是由于哈希碰撞的导致。
如果黑客使用精心设计的参数（这些参数可以根据jdk公开的哈希算法测试出来），通过HTTP请求，使用tomcat内部产生大量链表，消耗服务器的CPU，就会产生DoS（Denial of Service）。
因此：
Tomcat也对这种情况进行讨论。tomcat邮件