最新消息:从今天开始,做一个有好习惯的人。

java里集合这些事情-Map

java体系 迷路的老鼠 3386浏览 2评论

前面简单总结了一下集合,Map能说的可多可少,先按照自己想的总结吧

前面说到HashSet的时候也提到一点,HashSet的实现其实就是HashMap,所以HashMap的重复性校验也是基于HashCode和equals,所以对于对象来说,重写HashCode和equals是非要重要的。

HashMap的数据结构是哈希表,哈希表的容量在Map初始化时就会设定,默认为16,还有一个默认值是加载因子0.75,这个加载因子的含义是,当Map的真实容量到达了当前最大容量的0.75倍,就会立即进行扩容操作。

前面也提到了数据结构,数组和链表,两种方式的优缺点,哈希表的数据结构是数组和链表的结合,根据key进行hash散列成数组结构 (并不是一个Hash一个桶,通常是通过把Hash再取模放入一个桶 h & (table.length -1),Hash算法本质上是三步:取key的hashCode值、高位运算、取模运算),每个桶可能会存在多个对象(发生碰撞),会把这些hash后的对象以链表的形式进行存储,当hashCode取模到同一个桶,再根据key对链表的每一个值进行equals匹配取值。理论上提高了读取和操作的效率,同时也存在一个问题,就是扩容效率的问题。

为什么要扩容?前面说了会把key的hash之后取模放入一个桶中,当桶的数量比较少,发生碰撞的几率就比较大,一个桶中的链表长度非常大, 导致查询效率降低,这时就需要做扩容操作(理论需要,不是实际逻辑上的条件),让数据尽量分布均匀(谁知道均不均匀呢)。

JDK1.8里对链表部分有升级,当链表长度大于8时,对象的存储方式变成了红黑树节点,同样,如果删除某个val,导致长度小于8,也会将红黑树转成链表。主要是为了频繁发生碰撞导致链表长度过长,查询效率降低。


1
2
3
4
5
6
7
8
9
10
11
12
13
for (int binCount = 0; ; ++binCount) {
     if ((e = p.next) == null) {
         p.next = newNode(hash, key, value, null);
         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
             // 大于8时转为红黑树
             treeifyBin(tab, hash);
         break;
     }
     if (e.hash == hash &&
         ((k = e.key) == key || (key != null && key.equals(k))))
         break;
     p = e;
 }

HashMap有个子类LinkedHashMap,通过链表加哈希散列的方式,实现了有序性。

TreeMap和TreeSet比较类型,都是红黑树的实现方式,这里就不多说了,后面会专门写一篇文章对红黑树进行总结。

这里再总结一下Map相关的内容

  • LinkedHashMap比HashMap慢一点,因为它需要维护一个双向链表。
  • TreeMap比HashMap与Hashtable慢(尤其在插入、删除key-value时更慢),因为TreeMap底层采用红黑树来管理键值对。
  • 适用场景:
  • 一般的应用场景,尽可能多考虑使用HashMap,因为其为快速查询设计的。
  • 如果需要特定的排序时,考虑使用TreeMap。
  • 如果仅仅需要插入的顺序时,考虑使用LinkedHashMap。

转载请注明:迷路的老鼠 » java里集合这些事情-Map

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (2)

  1. 敲黑板,师傅传授的武功秘籍get好了喂~
    wa5年前 (2019-09-30)回复
    • 要考试的
      迷路的老鼠5年前 (2019-09-30)回复