HashMap总结使用+原理+面试

文章目录

- - 1.Hashmap的基本使用
  - - 创建hashmap对象。
    - 遍历hashmap
    - 统计字母出现的次数用来投票计算
    - 返回JSON数据
  - 2.hashmap源码阅读
  - - put源码阅读
  - 3. HashMap 面试题目
  - - hashmap实现的原理
    - 什么时候数组需要进行扩容
    - hashmap怎么确定把数据放到那个节点的哪个位置。
    - 为什么用 `n - 1` 与运算？
    - 计算哈希值比较高效的哈希函数有哪些？
    - 是否是线程安全
    - 扩容机制
    - 负载因子为什么是0.75
    - HashMap 允许空键（`null` key）和空值（`null` value`)吗？

1.Hashmap的基本使用

创建hashmap对象。

创建一个hashmap对象， put方法进行往里面添加值。

Map<String,String> map=new HashMap<>();
map.put("111","abc");
map.put("112","abcd");
map.put("1123","abcde");

遍历hashmap

//直接遍历 keySet()
for (String key : map.keySet()) {
    System.out.println(key + " " + map.get(key));
}

//如果只需要遍历value
for (String str : map.values()) {
    System.out.println(str);
}
//表示键值对的 Entry
for (Map.Entry<String, String> entry : map.entrySet()) {
    String key = entry.getKey();
    String value = entry.getValue();
}

//stream流
map.entrySet().forEach(entry -> {
    System.out.println(entry.getKey() + " " + entry.getValue());
});

统计字母出现的次数用来投票计算

map集合的作用，统计字母出现的次数，比如有一串字母，想要统计每一个字母出现的次数可以使用map的结构。

public static void main(String[] args) {
    String str = "aaabbbcccdddeee";
    Map<Character,Integer> map=new HashMap<>();
    for (int i = 0; i < str.length(); i++) {
        char c=str.charAt(i);
        if (map.containsKey(c)){
            Integer value=map.get(c);
            map.put(c,value+1);
        }else{
            map.put(c,1);
        }
    }
    System.out.println(map);
}

返回JSON数据

在开发中map还可以用来存储数据，然后返回给前端。如果后端返回的数据不固定，可以不设置VO类，直接用Map封装起来返回给前端，也是key-value的形式。

 Map<String, Object> map = new HashMap<>();
Integer id = selctedUser.getId();
        map.put("username", selctedUser.getUsername());
        map.put("id", id);
        String token = JWTUtil.createJWT("njitzx", 1000 * 3600 * 10, map);
        map.put("token", token);

@PostMapping("/login")
public Result login(@RequestBody User user) {
    Map<String, Object> map = userService.login(user);
    return Result.success(map);
}

2.hashmap源码阅读

hashmap的结构:

HashMap的成员变量:

transient Node<K,V>[] table; 哈希表结构中数组

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量是16

static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认的加载因子决定了hashmap的扩容时机.

hashmap每一个键值对对象中包含的元素:

链表中是Node

不是链表 TreeNode

hashmap创建的时候是懒加载创建，没有put的时候是空的。

直接创建一个空的HashMap，直接赋值因子，其他并没有创建。

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
}

put源码阅读

put方法调用，里面调用了putval方法。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
                                        //重复的数据覆盖
}

需要对key进行hash取值，放在数组的某个位置，这个hash函数就是为了分布均与一些，减少哈希碰撞。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
h ^ (h >>> 16)：然后将原哈希值 h 与其右移后的值做异或操作。异或操作的效果是将低 16 位和高 16 位的值混合，生成一个更均匀的哈希值。这有助于降低哈希碰撞的概率，尤其是在数据较多时，可以避免哈希值的分布过于集中。

putval方法

1.添加元素的时候，数组的位置为null.

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) == 0)
        n = (tab = resize()).length; //如果都为空 那么初始化这个数组

    i= (n - 1) & hash;  //计算索引的位置
    
    p = tab[i]
    if (p== null)  //hash值和n-l 与运算  不为空直接插入
        tab[i] = new Node(hash, key, value, null);  
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;  //添加的内容是相等的
        else if (p instanceof TreeNode) //p是否是树的节点
            e = ((TreeNode<K,V>)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);
                    //判断长度是否大于8   还有数组长度是否大于64 如果都满足 转为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;  //结束循环
                }
                  //出现了重复的内容  直接break
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;  //p往下移动一个   上面e=p.next  p=e;
            }
        }
        //p.next 复制给e了   当前需要覆盖元素的
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 是false 覆盖的    oldvalue不为空
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;   
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

3. HashMap 面试题目

hashmap实现的原理

jdk1.7之前hashmap实现的原理是数组+链表实现的。 Node[] tables；

jdk1.8之后，当数据量比较少的时候时数组+链表，数据量比价大的时候时数组+红黑树。当链表长度大于8，一个桶的元素超过了8会讲该桶转为红黑树。当总的数量大于64，并且桶内的链表长度大于8的时候，也会进行链表到红黑树转换。

什么时候数组需要进行扩容

HashMap 有一个负载因子（默认值是 0.75），它决定了何时扩容。负载因子表示数组已填充的程度，当数组中已有的元素数量超过数组容量与负载因子乘积时，HashMap 会进行扩容。

threshold 这个用来记录阈值的。扩容一般是两倍进行扩容。

hashmap怎么确定把数据放到那个节点的哪个位置。

对于每一个key就是hashi值，然后和n-1进行与运算确定节点存在哪个位置，然后如果是单链表还需要遍历单链表去找到这个节点存储的位置。

为什么用 `n - 1` 与运算？

当数组的大小是 2 的幂时，n - 1 的二进制表示是由多个 1 组成的，这样可以保证哈希值的低位能够正确地映射到数组的索引。例如，如果 n 为 16，那么 n - 1 为 15（二进制：1111）。通过 & 运算，只保留哈希值的低 4 位，可以均匀地将哈希值分布到数组的各个位置。

计算哈希值比较高效的哈希函数有哪些？

拿到hashcode之后和 h>>16 向右移动16位进行或运算，生成一个更加均匀的哈希值。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
h ^ (h >>> 16)：然后将原哈希值 h 与其右移后的值做异或操作。异或操作的效果是将低 16 位和高 16 位的值混合，生成一个更均匀的哈希值。这有助于降低哈希碰撞的概率，尤其是在数据较多时，可以避免哈希值的分布过于集中。

是否是线程安全

HashMap 不是线程安全的。在多线程环境下，如果多个线程同时访问并修改同一个 HashMap 实例，可能会导致数据不一致、死循环或者其他意外的行为。

put 和 get 并发时会导致 get 到 null

HashMap 在扩容时，通常会执行以下步骤：

创建一个更大的数组（newTab），通常是原数组的两倍大。
将旧数组中的所有元素迁移到新数组中，这个过程是逐个元素搬迁的。
最后，table = newTab 将哈希表的引用指向新的数组。

在扩容过程中，可能会有多个线程同时访问 HashMap，其中一个线程（线程 1）正在执行扩容操作，将旧数组的数据迁移到新的数组上，而另一个线程（线程 2）则可能在此时进行 get 操作，导致其读取到不一致的数据（比如访问到了尚未迁移的部分或读取到了一个空的哈希表）。

不安全可以从原子性的角度去考虑，不是原子性的操作，不安全。

ConcurrentHashMap 是一种高性能的线程安全 Map 实现，适用于高并发场景。

它支持并发读取和部分更新（写操作是分段锁的），避免了全表锁定，提高了并发性能。

扩容机制

HashMap 的扩容是通过 resize 方法来实现的，该方法接收一个新的容量 newCapacity，然后将 HashMap 的容量扩大到 newCapacity：

获取旧数组及容量：如果旧容量已经达到 HashMap 支持的最大容量 MAXIMUM_CAPACITY（ 2 的 30 次方），就将新的阈值 threshold 调整为 Integer.MAX_VALUE（2 的 31 次方 - 1）
创建新数组并转移元素：将旧数组 oldTable 中的元素转移到新数组 newTable 中。转移过程是通过调用 transfer 方法来实现的。该方法遍历旧数组中的每个桶，并将每个桶中的键值对重新计算哈希值后，将其插入到新数组对应的桶中。
重新计算阈值 threshold：转移完成后，方法将 HashMap 内部的数组引用 table 指向新数组 newTable，并重新计算阈值 threshold：