Hash算法：为快速查找而设计
1.普通查找（例如数组）：使用数组存储entry，查找 key=x的value时，需要去遍历entry，找出对应的entry才能找到value
2.hash查找：查找key=x，对key取hash值得到value的内存地址，因此hash算法的查找的复杂度是 O(1)
3.hashmap的hash算法：为了压缩hash存储时所需要的内存空间（所给予的空间是capacity ），执行以下逻辑
hash = hashcode(key) & （capacity -1）
4.hash = hashcode(key) & (capacity-1) 增大capacity可以降低hash冲突的概率，减小capacity可以节约内存空间
HashMap的原理
1.使用数组存储entry，每个entry保存了key和value
2.对于hash值相同的key，在entry出实现链表存储，即entry保存了next（entry）的引用
3.查找复杂度O(1)：只有没有hash冲突的理想情况下才是O(1)
4.hashmap扩容，根据hash=hashcode（key）& (capacity-1)，capacity大小发生了变化，因此hash发生了变化，所以hashmap扩容后各元素存储的顺序也可能发生变化
5.有hash冲突的查找时，先根据hash查找到存储位置，然后拿链表的key与查找的key进行比对，根据equals方法从该位置上的链表中取出该Entry
Hashtable HashMap ConcurrentHashMap
相同的：都集成了Map接口
不同点：
Hashtable
1.Hashtable的默认初始容量是11，负载因子是0.75，扩容是 X *2 + 1来实现的
2.get set等方法都是synchronize同步的
3.通过 enumeration枚举来进行遍历
4.key和value都不能是null
HashMap
1.HashMap 的默认初始容量是16，负载因子是0.75，扩容是 X *2来实现的
2.非同步，线程不安全
3.遍历用到的是数组和链表
4.可以接受一个null作为key，接受多个null作为value
ConcurrentHashMap
1.对entry进行分段segment，每个segment配锁，相当于hashtable的全局加锁，效果提高了
2.entry的 key，next都是final修饰的，所以concurrenthashmap的remove操作把，需要把要删除所在链表的entry都进行复制然后才能删除目标节点的entry
3.entry的value和next还有volatile修饰，保证每次修改都立即得到同步，保证线程安全
4.默认分为16段
5.相当于一个分段的hashtable 分段块进行加锁不用整体加锁，提高了效率