Java - 基础 - HashMap

2022-02-16 09:09:59

[TOC]

HashMap

1、基本概念

两个概念：

初始容量(桶) 负载因子

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

初始桶数：16

初始负载因子：0.75

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

2、看代码

2.1 类信息

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

public class HashMap<K,V> 
    extends AbstractMap<K,V>
    implements Map<K,V>, 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<K,V>[] table;                        // 保存桶元素的数组
transient Set<Map.Entry<K,V>> entrySet;                // 返回键值对数据
transient int size;                                    // 集合中元素个数
transient int modCount;                                // 当前结构被修改的次数，配合快速失败机制
          int threshold;                            // 记录桶中链表的数量

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

2.3 内部类Node及其内部方法

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

    // int hash:存放key哈希后的哈希值
    // key \ value :键值对
    // Node<K,V> next:单链表结构，指向下一个节点
    // 注：回忆内部类的使用方法，new 外部类.内部类().内部类方法();
    
    
        // 内部类的有参构造，进行参数赋值
        Node(int hash, K key, V value, Node<K,V> 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 新增节点扩容

// /**
     * 参数kc：新增节点key的类型
     * 参数k：新增节点的key
     * 参数x：当前节点的key
     *
     * 当前节点x的key为null
     * 或当前节点key的类型不同于新增节点key的类型
     * 返回0，否则返回k.compareTo(x)比较的结果
     */
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}



// /**
 * 扩容操作，返回给定目标容量大小的2次方
 */
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

2.6 构造方法

/* ---------------- Public operations -------------- */

// 好几种构造方法


// 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<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

3、根据上述抛出的一些疑问

3.1 为什么HashMap线程不安全

扩容时，多线程的并发操作会导致数据丢失（JDK 1.8里用resize函数修复）
并发执行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，来替换当前的链表，它使用哈希值来作为树的分支变量，这里的插入有两种情况

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

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

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

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

具体内容不细说了

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

四种

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

3.7 在JDK 1.7 和 JDK 1.8 的区别

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

码农公寓

Java - 基础 - 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、基本概念

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

相关文章