1.数据结构
数组+链表的形式 【】【】【】【】【】
| | | | |
【】【】【】【】【】
数组长度：固定，即初始化HashMap时的capacity。当需要数组长度时，会rehash，重新计算容器中所有值的位置
链表长度：可以扩展，即冲突的对象放入链表中
2.如何从map中寻找值
public V get(Object key) { Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); Entry<K,V> e = table[i]; while (true) { if (e == null) return null; if (e.hash == hash && eq(k, e.key)) return e.value; e = e.next; } } static int hash(Object x) { int h = x.hashCode(); h += ~(h << 9); h ^= (h >>> 14); h += (h << 4); h ^= (h >>> 10); return h; } static int indexFor(int h, int length) { return h & (length-1); }
a.计算hash值（计算hash值，采用这种旋转Hash函数的主要目的是让原有hashCode的高位信息也能被充分利用，且兼顾计算效率以及数据统计的特性）
b.通过hash值和capcity作位运算，获取数组中的index
c.在指定数组元素中，用equals索引链表，获得查询的值
3.几个变量
initialCapacity：初始化map中元素的个数的参数，不代表是最好map中最后设置的值
loadFactor：负载因子
capacity：Find a power of 2 >= initialCapacity，实际容量
threshold：capacity*loadFactor=threshold，当map中元素的数据>threshold时，capacity会double，然后会做最耗性能的resize
4.initialCapacity的参数值，一定要根据业务估算，否则可能会rehash，浪费性能
5.为何将capacity设为2的N次方？
因为java可以利用位运算作取模运算，提供运行速度
6.非线程安全的Map VS Collections.synchronizedMap
fail-fast机制（比如，循环遍历时，不能添加或者删除map中元素）
7.linkedHashMap VS LRU(最近最久未使用算法)
a.实现方式：HashMap的子类，利用双链表维持内部元素的关系
b.内部header、before、after3个指针引用
c.由于增加了维护链接列表的开支，其性能要比 HashMap 稍逊一筹，不过有一点例外：LinkedHashMap的迭代所需时间与其的所包含的元素成比例；而HashMap 迭代时间很可能开支较大，因为它所需要的时间与其容量（分配给Key空间的长度）成比例。一言以蔽之，随机存取用HashMap，顺序存取或是遍历用 LinkedHashMap。
d.缺省情况下，LinkedHashMap采取的更新策略是类似于队列的FIFO，如果你想实现更复杂的更新逻辑比如LRU（最近最少使用）等，将removeEldestEntry与accessOrder一起使用，就可以实现最基本的内存缓存。如果accessOrder被设置为true，则每次访问元素时，都将该元素移至head的前面，即链表的尾部。
8.WeakHashMap
a.强引用、软引用、弱引用、虚幻引用
b.WeakHashMap采用的策略是，只要作为key的对象已经不存在了（超出生命周期），就不会阻止垃圾收集器清空此条目，即使当前机器的内存并不紧张。
相关资源：敏捷开发V1.0.pptx
