java容器之HashMap

Wesley13
• 阅读 846

HashMap采用了数组和链表的数据结构,能在查询和修改方便继承了数组的线性查找和链表的寻址修改,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的。

解决哈希冲突的三个方法:

a.开放定址法

    又被称为再散列法,包括线性探测再散列、二次探测再散列、伪随机探测再散列

b.再哈希法

    地址冲突后,对哈希结果再次进行哈希,直到不冲突为止

c.链地址法

    冲突后的元素组成一个链指向当前地址(HashMap采用的该方式,只是当链表长度超过8后,就会把链表改为红黑树)

以下是具体的put过程(JDK1.8版)

1、对Key求Hash值,然后再计算下标

2、如果没有碰撞,直接放入数组中(碰撞的意思是计算得到的Hash值相同,需要放到同一个bucket中)

3、如果碰撞了,以链表的方式链接到后面

4、如果链表长度超过阀值( TREEIFY THRESHOLD==8),就把链表转成红黑树,链表长度低于6,就把红黑树转回链表

5、如果节点已经存在就替换旧值

6、如果数组满了(容量16*加载因子0.75),就需要 resize(扩容2倍后重排)

选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。

 下面从初始化一个HashMap及put一个键值对,来看下HashMap的resize()

Map exampleMap = new HashMap();

初始化Map则,可以看到exampleMap中,loadFactor是默认值0.75(loadFactor用于设置阈值,即到什么程度执行resize操作)

 exampleMap.put("1",1)

map中放入数据,看下源代码做了什么

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {//hash是1的hash值,key是字符串1,value是1
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)//tab的length是16,n的值是16
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)//按一定的规则,确定新增的参数放在tab数组的tab[i]位置,如果该位置为空,则直接初始化Node放入该位置;
        tab[i] = newNode(hash, key, value, null);
    else {//如果tab[i]不为空进入该分支
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))//如果hash相同,key相同,则替换tab[i]
            e = p;
        else if (p instanceof TreeNode)//判断如果tab[i]是treeNode,则把当前数据放入红黑树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {//如果tab[i]是普通Node,则在tab[i]维护的链尾部新增,当链接的Node数量大于8后,要把链改为红黑树结构存储
            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
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)//添加Node之后判断当前map中数据量是否大于12(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR),如果大于需要resize,否则结束当前操作
        resize();
    afterNodeInsertion(evict);
    return null;
}
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Stella981 Stella981
3年前
HashMap中神奇的h & (length
众所周知,HashMap是基于Hash表的Map接口实现,HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。但是知道了Hash值之后,又是怎么确定出key在数组中的索引呢?根据源码得知如下方法static
Wesley13 Wesley13
3年前
Java8 HashMap详解
Java8HashMapJava8对HashMap进行了一些修改,最大的不同就是利用了红黑树,所以其由数组链表红黑树组成。根据Java7HashMap的介绍,我们知道,查找的时候,根据hash值我们能够快速定位到数组的具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
3年前
Hash算法解决冲突的四种方法
Hash算法解决冲突的方法一般有以下几种常用的解决方法 1,开放定址法: 所谓的开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入 公式为:fi(key)(f(key)di)MODm(di1,2,3,……,m1) ※用开放定址法解决冲突的做法是:当冲突发
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
3年前
Java 之 HashMap 集合
一、HashMap概述java.util.HashMap<k,v集合implementsMap<k,v接口HashMap集合的特点:1、HashMap集合底层是哈希表:查询速度特别的快JDK1.8之前:数组单向链表JDK1.8之后:数组单向链表|红黑树(