03-01 01:25 南京工程学院 Java 发布于江苏

关注

HashMap知识整理

Hashmap的基本使用

创建hashmap对象。

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

Map<String,String> map=new HashMap<>();
map.put("111","abc");
map.put("112","abcd");
map.put("1123","abcde");   
//hashmap允许有一个键是null,在hashcode的时候会放第一位上面。  默认是没有重复的键的
可以map.put(null,123)

遍历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流+lamada表达式遍历
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);
}

发送 HTTP 请求的时候，需要构建请求体或者查询参数，可以用 map 存储需要请求的参数，构建 HTTP 请求。

缓存一些键值对的静态数据。

hashmap源码阅读

hashmap的结构:

HashMap的成员变量:

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

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量是16 数组默认的大小是 16

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//默认的加载因子决定了hashmap的扩容时机. 当哈希表中的元素等于长度*加载因子的时候，hashmap 需要进行扩容。

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

链表中是Node 存储的内容 key value next 还有 hash 值

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函数就是为了分布均与一些，减少哈希碰撞。

JDK1.8 求 hash 值，如果为 null，hash 值为 0，存在数组下等于 0 的地方。

先求出 hashcode，再右移动 16 位进行异或操作。让低位 16 位和高位 16 位的值混合，生成一个更加均匀的 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;  //设置长度为2的幂次方倍数在这边可以快速计算
    
    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;
}

HashMap 面试题目

介绍一下 Hashmap

hashmap 是一个可以实现快速查找、插入和删除的数据结构，时间复杂度是 O（1），在 jdk1.7 是基于数组+链表来实现的，jdk1.8 之后改成了数组+链表红黑树来实现。

hashmap的原理

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

jdk1.8之后，当数据量比较少的时候时数组+链表，数据量比价大的时候时，链表长度大于 8 的时候，数组+红黑树。当链表长度大于8，一个桶的元素超过了8 将桶转为红黑树。

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

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

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

为什么是两倍进行扩容?

hashmap 的容量都是 2 的幂次方倍数，

保证新容量始终为 2 的幂，这样在计算索引时可以用 (n - 1) & hash 来替代取模运算，从而提高计算效率。

应该是 hash 值&length，但是可以通过（n-1）&hash,这样提高了计算的效率。

在重新散列（rehash）过程中，每个元素只需根据其 hash 值的某一位判断：要么保持在原来的位置，要么移动到原索引加上旧容量的位置，从而降低了重新分布的计算开销。

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

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

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

出来的 hash 值应该是和 length 进行取模操作,但是取模操作底层太慢了,因为长度是 2 的 n 次方,

n-1 是二进制有多个 n-1 组成的. 通过疑惑运算可以只保留 hash 值低的几位.

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

拿到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 操作，导致其读取到不一致的数据（比如访问到了尚未迁移的部分或读取到了一个空的哈希表）。一个线程正在迁移另一个在 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：

使用 ConcurrentHashMap