7
HashMap 通过 hashcode 对其内容进行快速查找，而 TreeMap 中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结
果你就应该使用 TreeMap（HashMap 中元素的排列顺序是不固定的）。
HashMap：适用于在 Map 中插入、删除和定位元素。
Treemap：适用于按自然顺序或自定义顺序遍历键(key)。
HashMap 通常比 TreeMap 快一点(树和哈希表的数据结构使然)，建议多使用 HashMap，在需要排序的 Map 时候才用 TreeMap。
hashMap,hashTable, ConcurrentHashMap
HashTable
底层数组+链表实现，无论 key 还是 value 都不能为 null，线程安全，实现线程安全的方式是在修改数据时锁住整个 HashTable，效
率低，ConcurrentHashMap 做了相关优化
初始 size 为 11，扩容：newsize = olesize*2+1
计算 index 的方法：index = (hash & 0x7FFFFFFF) % tab.length
HashMap
底层数组+链表实现，可以存储 null 键和 null 值，线程不安全
初始 size 为 16，扩容：newsize = oldsize*2，size 一定为 2 的 n 次幂
扩容针对整个 Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
当 Map 中元素总数超过 Entry 数组的 75%，触发扩容操作，为了减少链表长度，元素分配更均匀
计算 index 方法：index = hash & (tab.length – 1)
HashMap 的初始值还要考虑加载因子:
哈希冲突：若干 Key 的哈希值按数组大小取模后，如果落在同一个数组下标上，将组成一条 Entry 链，对 Key 的查找需要遍历 Entry
链上的每个元素执行 equals()比较。
加载因子：为了降低哈希冲突的概率，默认当 HashMap 中的键值对达到数组大小的 75%时，即会触发扩容。因此，如果预估容
量是 100，即需要设定 100/0.75＝134 的数组大小。
空间换时间
：如果希望加快
Key
查找的时间，还可以进一步降低加载因子，加大初始大小，以降低哈希冲突的概率。
HashMap 和 Hashtable 都是用 hash 算法来决定其元素的存储，因此 HashMap 和 Hashtable 的 hash 表包含如下属性：
容量（capacity）： hash 表中桶的数量
初始化容量（initial capacity）：创建 hash 表时桶的数量，HashMap 允许在构造器中指定初始化容量
尺寸（size）：当前 hash 表中记录的数量
负载因子（load factor）：负载因子等于“size/capacity”。负载因子为 0，表示空的 hash 表，0.5 表示半满的散列表，依此类推。轻负载的
散列表具有冲突少、适宜插入与查询的特点（但是使用 Iterator 迭代元素时比较慢）
除此之外，hash 表里还有一个“负载极限”，“负载极限”是一个 0～1 的数值，“负载极限”决定了 hash 表的最大填满程度。当 hash
表中的负载因子达到指定的“负载极限”时，hash 表会自动成倍地增加容量（桶的数量），并将原有的对象重新分配，放入新的桶内，这
称为 rehashing。
HashMap 和 Hashtable 的构造器允许指定一个负载极限，HashMap 和 Hashtable 默认的“负载极限”为 0.75，这表明当该 hash 表的
3/4 已经被填满时，hash 表会发生 rehashing。
“负载极限”的默认值（0.75）是时间和空间成本上的一种折中：
较高的“负载极限”可以降低 hash 表所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的操作（HashMap 的 get()
与 put()方法都要用到查询）
剩余42页未读，继续阅读
