java集合–HashMap（三）

1.HashMap原理的简单概述

在前面两节我们搞懂了equals()方法和hashCode()方法，同时明白了什么是散列集和HashMap的基本用法。古人说：知其然知其所以然。我们知道怎样使用HashMap，我们还有必要知道其原理，这一节可能需要重复读好几遍才能看明白。

get()方法

当我们调用get()方法时，会先通过hash值计算出key从而找到该元素在桶（bucket）的位置。如果该位置上只有一个元素则直接命中，即找到。如果该不止一个元素，则会调用equals()方法遍历链表进行比较，如果找到即返回该值，没有找到则返回为空。
put()方法

当我们调用put()方法时，会先通过hash值计算出key映射到哪个桶（bucket）。如果桶上没有碰撞冲突（即该桶上没有元素），则直接插入。如果出现碰撞冲突，则以链表的方式插入。

2.HashMap属性介绍

基本属性

//默认的初始容量为 16
static final int DEFAULT_INITIAL_CAPACITY =  << ;

//最大的容量上限为 2^30
static final int MAXIMUM_CAPACITY =  << ;

//默认的负载因子为 0.75
static final float DEFAULT_LOAD_FACTOR = f;

//变成树型结构的临界值为 8
static final int TREEIFY_THRESHOLD = ;

//恢复链式结构的临界值为 6
static final int UNTREEIFY_THRESHOLD = ;

//哈希表
transient Node<K,V>[] table;

//哈希表中键值对的个数
transient int size;

//哈希表被修改的次数
transient int modCount;

//它是通过 capacity*load factor 计算出来的，当 size 到达这个值时，就会进行扩容操作
int threshold;

//负载因子
final float loadFactor;

//当哈希表的大小超过这个阈值，才会把链式结构转化成树型结构，否则仅采取扩容来尝试减少冲突
static final int MIN_TREEIFY_CAPACITY = ;

静态内部类

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

上面是Node 类的定义，它是 HashMap 中的一个静态内部类，哈希表中的每一个节点都是 Node 类型。我们可以看到，Node 类中有 4 个属性，其中除了 key 和value 之外，还有 hash 和 next 两个属性。hash 是用来存储 key 的哈希值的，next是在构建链表时用来指向后继节点的。

3.HashMap方法介绍

get()方法

//get 方法主要调用的是 getNode 方法，所以重点要看 getNode 方法的实现
        public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

        final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

        //如果哈希表不为空 && key 对应的桶上不为空
        if ((tab = table) != null && (n = tab.length) >  &&
            (first = tab[(n - ) & hash]) != null) {
            //是否直接命中
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
                //判断是否有后续节点
            if ((e = first.next) != null) {
            //如果当前的桶是采用红黑树处理冲突，则调用红黑树的 get 方法去获取节点
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    //不是红黑树的话，那就是传统的链式结构了，通过循环的方法判断链中是否存在该 key
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

实现步骤大致如下：

1、通过 hash 值获取该 key 映射到的桶。

2、桶上的 key 就是要查找的 key，则直接命中。

3、桶上的 key 不是要查找的 key，则查看后续节点：

（1）如果后续节点是树节点，通过调用树的方法查找该 key。

（2）如果后续节点是链式节点，则通过循环遍历链查找该 key。

put()方法

//put 方法的具体实现也是在 putVal 方法中，所以我们重点看下面的 putVal 方法
 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果哈希表为空，则先创建一个哈希表
        if ((tab = table) == null || (n = tab.length) == )
            n = (tab = resize()).length;
        //如果当前桶没有碰撞冲突，则直接把键值对插入，完事
        if ((p = tab[i = (n - ) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //如果桶上节点的 key 与当前 key 重复，那你就是我要找的节点了
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果是采用红黑树的方式处理冲突，则通过红黑树的 putTreeVal 方法去插入这个键值对
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //否则就是传统的链式结构
            else {
            //采用循环遍历的方式，判断链中是否有重复的 key
                for (int binCount = ; ; ++binCount) {
                //到了链尾还没找到重复的 key，则说明 HashMap 没有包含该键
                    if ((e = p.next) == null) {
                    //创建一个新节点插入到尾部
                        p.next = newNode(hash, key, value, null);
                        //如果链的长度大于 TREEIFY_THRESHOLD 这个临界值，则把链变为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - ) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //找到了重复的 key
                    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)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

put 方法比较复杂，实现步骤大致如下：

1、先通过 hash 值计算出 key 映射到哪个桶。

2、如果桶上没有碰撞冲突，则直接插入。

3、如果出现碰撞冲突了，则需要处理冲突：

（1）如果该桶使用红黑树处理冲突，则调用红黑树的方法插入。

（2）否则采用传统的链式方法插入。如果链的长度到达临界值，则把链转变为红

黑树。

4、如果桶中存在重复的键，则为该键替换新值。

5、如果 size 大于阈值，则进行扩容。

remove()方法

//remove 方法的具体实现在 removeNode 方法中
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //如果当前 key 映射到的桶不为空
    if ((tab = table) != null && (n = tab.length) >  &&
        (p = tab[index = (n - ) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //如果桶上的节点就是要找的 key，则直接命中
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            //如果是以红黑树处理冲突，则构建一个树节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            //如果是以链式的方式处理冲突，则通过遍历链表来寻找节点    
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //比对找到的 key 的 value 跟要删除的是否匹配
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
             //通过调用红黑树的方法来删除节点              
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
             //使用链表的操作来删除节点
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

删除和插入的步骤差不多。

上面就是关于HashMap属性和方法的主要介绍。代码有点长，读者初读可以不必在意细节，只需要了解HashMap的get()和put()的原理。

java集合–HashMap（四）

java集合--HashMap（三）java集合–HashMap（三）

java集合–HashMap（三）

继续阅读

关于Gradle配置的小结

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method