【上海校区】HashMap的工作原理 - 黑马程序员技术交流社区

简单说下HashMap的实现原理：

首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中

即HashMap的原理图是：

一，JDK1.8中的涉及到的数据结构

transient Node[] table;//存储（位桶）的数组

2，数组元素Node实现了Entry接口

//Node是单向链表，它实现了Map.Entry接口

[Java] 纯文本查看 复制代码

static class Node implements Map.Entry {

    final int hash;

    final K key;

    V value;

    Node next;

    //构造函数Hash值 键 值 下一个节点

    Node(int hash, K key, V value, Node 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;

    }

//判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true

    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;

    }

[Java] 纯文本查看 复制代码

//红黑树

static final class TreeNode extends LinkedHashMap.Entry {

    TreeNode parent;  // 父节点

    TreeNode left; //左子树

    TreeNode right;//右子树

    TreeNode prev;    // needed to unlink next upon deletion

    boolean red;    //颜色属性

    TreeNode(int hash, K key, V val, Node next) {

        super(hash, key, val, next);

    }

  //返回当前节点的根节点

    final TreeNode root() {

        for (TreeNode r = this, p;;) {

            if ((p = r.parent) == null)

                return r;

            r = p;

        }

    }

下载附件

2018-9-14 18:00 上传