Java集合——HashMap

Java集合——HashMap

• HashMap
• • 哈希表
  • 初始容量
  • • 加载因子
  • 常用方法
  • 代码示例
  • • Person类重写hashCode和equals
    • 测试
    • 结果
  • 源码分析
  • • 默认容量
    • 最大容量
    • 加载因子
    • 链表长度为8转为红黑树
    • 最小树容量
    • Node容器
    • 无参构造
    • put方法如何添加元素
    • • 调用hash方法设置hash值
      • 调用putVal方法
      • • 1.HashMap中无元素添加时
      • 2.有元素添加
    • 扩容

HashMap

基于哈希表的Map实现

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。

HashMap 是无序的，即不会记录插入的顺序。

HashMap 的 key 与 value 类型可以相同也可以不同，可以是字符串（String）类型的 key 和 value，也可以是整型（Integer）的 key 和字符串（String）类型的 value。

HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。

哈希表

Hashtable类提供了一种在用户定义键结构的基础上来组织数据的手段

例如，在地址列表的哈希表中，你可以根据邮政编码作为键来存储和排序数据，而不是通过人名

哈希表键的具体含义完全取决于哈希表的使用情景和它包含的数据

初始容量

默认初始为16，加载因子0.75的空HashMap

加载因子

0.75指当容器容量达到75%就进行扩容

常用方法

方法名	说明
clear()	删除 hashMap 中的所有键/值对
clone()	复制一份hashMap
isEmpty()	判断hashMap是否为空
size()	计算hashMap 中键/值对的数量
put()	将键/值对添加到 hashMap中
putAll()	将所有键/值对添加到 hashMap 中
putlfAbsent()	如果hashMap中不存在指定的键，则将指定的键/值对插入到 hashMap 中。
remove()	删除hashMap中指定键key的映射关系
containsKey()	检查hashMap中是否存在指定的key 对应的映射关系。
containsValue()	检查hashMap 中是否存在指定的value 对应的映射关系。
replace( ）	替换hashMap中是指定的key 对应的value。
replaceAll()	将hashMap 中的所有映射关系替换成给定的函数所执行的结果。
get()	获取指定key 对应对value
getOrDefault()	获取指定key对应对value，如果找不到key，则返回设置的默认值
forEach()	对hashMap中的每个映射执行指定的操作。
entrySet()	返回hashMap 中所有映射项的集合集合视图。
keySet()	返回hashMap中所有key组成的集合视图。
values()	返回hashMap中存在的所有value值
merge()	添加键值对到 hashMap中
compute()	对hashMap中指定 key的值进行重新计算
computelfAbsent()	对hashMap中指定key的值进行重新计算，如果不存在这个key，则添加到hasMap中
computelfPresent()	对hashMap中指定key 的值进行重新计算，前提是该key存在于hashMap中。

代码示例 Person类重写hashCode和equals

package map.entity;

import java.util.Objects;

public class Person {
    private Integer id;
    private String name;

    public Person() {
    }

    public Person(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof Person)) {
            return false;
        }
        Person person = (Person) o;
        return Objects.equals(id, person.id) && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Person{" +
                "id=" + id +
                ", name='" + name + ''' +
                '}';
    }
}

测试

package map;

import map.entity.Person;

import java.util.HashMap;

public class Demo2 {
    public static void main(String[] args) {
        HashMap data = new HashMap<>();
        data.put("1", new Person(1, "zhangsan"));
        data.put("2", new Person(2, "lisi"));
        data.put("3", new Person(3, "wangwu"));
        Object o = data.get("2");
        System.out.println(o);
        System.out.println("=======================");
        data.forEach((x, y) -> {
            System.out.println(x + "|" + y);
        });
        System.out.println(data.size());
        System.out.println(data.isEmpty());
        System.out.println("=======================");
        System.out.println(data.values());
        data.clear();

    }
}

结果

源码分析 默认容量

1<<4表示1向右移四位，即：1 × 2 × 2 × 2 × 2 = 16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

最大容量

2的30次方：1,073,741,824

static final int MAXIMUM_CAPACITY = 1 << 30;

加载因子

达到容量的75%进行扩容

static final float DEFAULT_LOAD_FACTOR = 0.75f;

链表长度为8转为红黑树

条件：存储数组达到64（大于等于64），存储链表达到8时转化为红黑树

static final int TREEIFY_THRESHOLD = 8;

最小树容量

static final int MIN_TREEIFY_CAPACITY = 64;

Node容器

我们可以发现有键有值来构成键值对，有hash值进行判断，有next这个可以理解为C中的指针，next用于指向下一个Node

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

        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;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;

            return o instanceof Map.Entry e
                    && Objects.equals(key, e.getKey())
                    && Objects.equals(value, e.getValue());
        }
    }

无参构造

无参构造中仅是将加载因子进行了设置

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

put方法如何添加元素

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                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)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

调用hash方法设置hash值

对key进行判断，若key！=null 则返回Object类中的hashCode方法来设置hash值其中还会进行^异或h>>>无符号右移16位，最后hash值就产生了

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

调用putVal方法

由于直接用语言描述很难所以我下面就用手写画图的方式

1.HashMap中无元素添加时

2.有元素添加

扩容

每次容量的75%进行扩容，扩容后是原来容量的2倍
核心是这行

else if ((newCap = oldCap << 1)

 final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }