java 集合的学习网址
原创
2017-12-02
java

参考地址

Java 集合学习指南
HashMap和HashTable到底哪不同?
HashMap 在 JDK 1.8 后新增的红黑树结构
hash函数为什么要选择对素数求余?

HashMap

  • “链表散列”:HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。
  • rehash,resize 扩容:需要重新计算每个元素的位置。
  • JDK 1.8中,采用红黑树,映射到同一个哈希桶(数组位置)的Entry对象,使用了红黑树来存储,从而大大加速了其查找效率。
  • HashMap是支持null键和null值的;null键存在数组0的位置,参考如下代码
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
  • DEFAULT_INITIAL_CAPACITY = 1 << 4; 初始大小16(1 << 4), 2的幂次增长,加快hash计算,只需要于不需要除法。
  • MAXIMUM_CAPACITY = 1 << 30; 再大就溢出了,-2147483648 == 1<<31
  • DEFAULT_LOAD_FACTOR = 0.75f; 默认加载因子,越大散列之后冲突越多,越小浪费的空间就多。
  • TREEIFY_THRESHOLD = 8;红黑树的阈值,大于8,链表采用红黑树优化查询效率。

Hashtable

  • 历史遗留api;名字就不遵守驼峰,
  • 线程安全,就是公开的方法比如get都使用了synchronized描述符。而遍历视图比如keySet都使用了Collections.synchronizedXXX进行了同步包装。
  • this(11, 0.75f); 默认初始容量11,加载因子0.75;增长速度2n+1;采用素数,奇数,哈希表的大小为素数时,简单的取模哈希的结果会更加均匀,但hash计算时,hashmap的位运算较快。