集合HashMap原理解析

文章目录

• HashMap
• • 1、基本概念
  • 2、看代码
  • • 2.1 类信息
    • 2.2 类属性
    • 2.3 内部类Node及其内部方法
    • 2.4 外部类方法
    • 2.5 新增节点扩容
    • 2.6 构造方法
  • 3、根据上述抛出的一些疑问
  • • 3.1 为什么HashMap线程不安全
    • 3.2 为什么初始负载因子为0.75
    • 3.3 时间复杂度为多少
    • 3.4 树化的过程
    • 3.5 为什么链表的长度为8时变成红黑树？为什么为6时又变成链表？
    • 3.6 HashMap提供了多少种构造方法
    • 3.7 在JDK 1.7 和 JDK 1.8 的区别
• over

HashMap 1、基本概念

两个概念：

初始容量(桶) 负载因子

当哈希表中的条目数 > ( 负载因子 * 当前容量 ) 时，哈希表将进行扩容，以便哈希表拥有大约两倍的桶数

初始桶数：16

初始负载因子：0.75

与Hashtable的区别：HashMap是非线程安全的，Hashtable是线程不安全的

2、看代码 2.1 类信息

继承一个抽象类，三个接口

public class HashMap 
	extends AbstractMap
	implements Map, Cloneable, Serializable {}

Cloneable接口：实现clone方法来进行深浅克隆

Serializable接口：对象序列化接口

什么时候需要用到序列化？

需要把对象的状态进行网络传输 or 对象信息持久化

private static final long

 serialVersionUID = 362498820763181265L;

该参数就是设置字节流的UID来进行序列化动作

2.2 类属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 	// aka 16 初始容量
static final int MAXIMUM_CAPACITY = 1 << 30;		// 最大容量，1 * 2 的30次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;		// 初始负载因子
static final int TREEIFY_THRESHOLD = 8;				// 桶中链表个数超过8时转换为红黑树
static final int UNTREEIFY_THRESHOLD = 6;			// 桶中链表个数小于6时转换为链表

static final int MIN_TREEIFY_CAPACITY = 64;			
// 桶后链表被树化时，最小的hash表容量
// 散列表容量小于64时，就算桶后数量超过8，也不会树化，只会扩容

// transient 属性不会被序列化
transient Node[] table;						// 保存桶元素的数组
transient Set> entrySet;				// 返回键值对数据
transient int size;									// 集合中元素个数
transient int modCount;								// 当前结构被修改的次数，配合快速失败机制
		  int threshold;							// 记录桶中链表的数量

final float loadFactor;
// 负载因子，用来衡量hashmap 满的程度，影响扩容时机，默认值为0.75
// 实时计算负载因子的公式：size / capacity，集合元素个数 除以 当前容量

2.3 内部类Node及其内部方法

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

    // int hash:存放key哈希后的哈希值
    // key  value :键值对
    // Node next:单链表结构，指向下一个节点
    // 注：回忆内部类的使用方法，new 外部类.内部类().内部类方法();
    
    
    	// 内部类的有参构造，进行参数赋值
        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    	
		// 这里是一些get获取数据的操作
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

    	// 方法hashCode() = 键哈希 ^ 值哈希
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

    	// 传入新的值，对现值value进行赋值，返回oldValue
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

    	// equals方法，如果地址相等返回true，
    	// 如果对象o是Map.Entry的子类或子接口，
    	// 		再进行两轮equals比较，如果跟比较的键值都相等，返回true
    	// 上述情况都未命中，返回false
        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;
        }
    }

2.4 外部类方法

// 对传入的对象进行哈希
// 如果key是空，返回0
// 否则返回 int = (h = key.hashCode()) ^ (h >>> 16))
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}


static Class comparableClassFor(Object x) {
    if (x instanceof Comparable) {	
        // 判断是否实现了Comparable接口
        // Comparable 接口，排序用的
		// 实现了 Comparable 接口的类通过实现 comparaTo 方法从而确定该类对象的排序方式
        Class c; 
        Type[] ts, as; 
        ParameterizedType p;
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;	//如果运行时类型是String，就返回String.class
        if ((ts = c.getGenericInterfaces()) != null) {	
            // 判断是否有直接实现的接口 getGenericInterfaces
            // 它返回表示 由该类对象所表示的类或接口 直接实现的接口 的Types对象
            // 通俗的说，这是个反射方法，获得这个对象所实现的所有接口
            // 你都没实现接口，当然为 null
            for (Type t : ts) {
                // 遍历直接实现的接口
                if ((t instanceof ParameterizedType) &&
                    ((p = (ParameterizedType) t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) 
                    // type arg is c
                    // 一堆的条件，不想看了，反正命中这些条件就返回Class对象c
                    return c;
            }
        }
    }
    return null;	// 都没有命中则返回 null
}


// 判断集合是否为空
public boolean isEmpty() {
        return size == 0;
    }

2.5 新增节点扩容

// 

// 好几种构造方法


// 1 提供桶数和负载因子
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}


// 2 提供桶数
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


// 3 默认值，什么都不给
//	初始桶数：16
//	初始负载因子：0.75
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


// 4 传入Map对象
public HashMap(Map m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

3、根据上述抛出的一些疑问 3.1 为什么HashMap线程不安全

1. 扩容时，多线程的并发操作会导致数据丢失（JDK 1.8里用resize函数修复）
2. 并发执行Put时，会发生数据覆盖的情况

两个线程同时put的时候，已经通过哈希算法算出下标是相同的，其中一个线程可能由于时间片耗尽被挂起，另外一个线程直接插入，由于这个时候两个线程都计算完了哈希的下标，所以这个时候另外一个线程唤醒后，不会进行判断，而是直接插入，导致把之前线程插入的数据进行覆盖，变得不安全

3.2 为什么初始负载因子为0.75

时间和空间的复杂度权衡

如果是0.5，虽然时间效率提升了，但是空间利用率降低了

如果是 1 ，虽然空间利用率上去了，但是时间效率降低了

3.3 时间复杂度为多少

首先要先了解，什么是时间复杂度

然后根据Map的Get和Put方法进行判断时间复杂度为多少

HashMap的时间复杂度分析 - 简书 (jianshu.com)

3.4 树化的过程

当这个链表的长度大于8时，就会进行红黑树化

TREEIFY_THRESHOLD = 8

红黑树是什么？特殊的二叉查找树

文章
红黑树(一)之 原理和算法详细介绍 - 如果天空不死 - 博客园 (cnblogs.com)
3分钟让你明白：HashMap之红黑树树化过程_mifffy_java的-CSDN博客

通过动态实现一个TreeMap，来替换当前的链表，它使用哈希值来作为树的分支变量，这里的插入有两种情况

1. 如果哈希值不等，但是指向同一个桶子，比较大的那个就会往右子树插
2. 如果哈希值相等，最好key值能实现了Comparable接口，来实现排序插入，但是是否实现非必须

因为如果发生hash碰撞的话就 emmmmm（不同的数据计算出的hash值是一样的）

3.5 为什么链表的长度为8时变成红黑树？为什么为6时又变成链表？

其实是时间与空间的权衡，尽量保证相互之间的复杂度都为最低

具体内容不细说了

3.6 HashMap提供了多少种构造方法

四种

1. 默认无参构造，按照给定的初始值进行初始化
2. 提供桶数
3. 提供桶数和负载因子
4. 传入Map对象

3.7 在JDK 1.7 和 JDK 1.8 的区别

1. 在JDK 1.7中，HashMap采用桶+链表的概念来实现，但是存在缺点；当同一Hash值的元素都放在一个桶后的链表，就会导致链表过长，查找效率过低
2. 在JDK 1.8后，出现了桶+链表+红黑树的概念；当链表长度超过默认值8的时候，就会转换成红黑树，解决了1.7中链表过长导致查找效率低的问题

over