对比Hashtable、HashMap、TreeMap有什么不同? - 《java核心技术》笔记

简单回答:

  • hashtable是同步的,不支持null的键值;
  • HashMap不是同步的,支持null的键值,put和get可以达到常数时间的性能;
  • TreeMap基于红黑树,put、get、remove都是O(log(n))

266cfaab2573c9777b1157816784727c

注意点:HashMap的性能表现非常依赖于哈希码的有效性,需要注意:

  • equals相等的话,hashCode一定要相等,所以重写了hashCode也要重写equals;
  • hashCode需要保持一致性,状态改变返回的哈希值仍然要一致;
  • equals的对称、反射、传递等特性

HashMap基于哈希思想,当调用put()时,它调用键对象的hashCode()方法来计算hashCode,然后找到bucket位置存储值对象。当get()时,通过键对象的equals()方法找到正确的键值对。HashMap使用链表来解决碰撞问题,碰撞了后会存储在链表的下一个节点中。如果链表大小超出阈值(TREE_IFY_THRESHOLD,8),链表会被改造为树形结构。

解决哈希冲突的常见方法:

  • 开放寻址,如果p1=H(key)冲突了,则计算p2=H(p1),直到找到一个不冲突的。
  • 再哈希法,同时构造多个不同的哈希函数,找到一个不冲突的。
  • 链地址法,将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存放在哈希表的第i个单元中。
  • 建立公共溢出区,将哈希表分为基本表和溢出表,凡是和基本表发生冲突的元素,一律填入溢出表。
comments powered by Disqus