1. HashMap 的底层原理

在JDK1.8之前, 哈希表底层采用了 数组 + 链表 实现, 同一hash值的链表都存储在一个链表里, 当同一hash值元素过多时, 通过key值依次查询的效率较低.

在JDK1.8时, 哈希表底层采用了 数组 + 链表 + 红黑树 实现, 当链表的长度超过8个, 此时的数组长度大于64, 将链表转换成红黑树, 减少了搜索的时间. 当链表长度变成6的时候, 红黑树再转换成链表.

哈希表的 key 和 value 都可以存储null

2. 哈希表扩容机制

哈希表的容量Capacity, 默认是 16

负载因子LoadFactor, 默认是 0.75

当 哈希表的大小 > Capacity * LoadFactor, 此时哈希表就需要扩容. 一般是2倍扩容. 扩容之后, 重新计算每个元素在HashMap中的位置数组.

如果用户设置了容量, 并不会直接作为默认容量, 而是会进行计算, 从而得到一个 2的幂, 然后作为哈希表的容量.

哈希表的容量一定是 2 ^ n

3. 什么是哈希冲突? 解决哈希冲突的方法?

哈希冲突: 如果两个对象通过相同的哈希函数计算出相同的 HashCode 相同, 这种现象称为 hash冲突.

解决哈希冲突的方法:
① 开放定址法
当发生哈希冲突时, 如果哈希表未被装满, 说明在哈希表中必然还有空位置, 那么可以把把 key 存放到冲突位置的 "下一个位置"去

② 链地址法
对于相同的值, 使用链表进行链接. 使用数组存在每一个链表.

③ 再 hash 法
通过某个hash函数计算的key存在冲突的时候, 再用另外的hash函数对这个key做hash, 一致运算直到不再产生冲突.

④ 建立公共溢出区
把hash表分为两个部分, 一个为基本表, 一个为溢出表. 凡是存在冲突的元素, 一律放入到溢出表中.

4. HashMap, HashTable的区别

底层数据结构不同:
在jdk1.7 底层都是数组 + 链表, 但 HashMap 在jdk1.8, 加入了红黑树.
键值取值不同:
HashTable 不允许键值为null, HashMap的键值都可以为null
哈希值算法不同:
HashMap添加元素, 使用了自定义的哈希算法.而HashTable直接使用了key的hashCode()
初始化容量不同:
HashMap的初始容量为 16, HashTable的初始容量为 11
扩容机制不同:
HashMap扩容机制是两倍扩容(2n), HashTable扩容机制是两倍+1扩容(2n+1)
实现方法不同:
HashMap继承 AbstractMap 类, HashTable 继承 Dictionary 类
迭代器不同:
HashMap迭代器是Iterator, HashTable迭代器是enumerator
线程安全性不同:
HashMap线程不安全, HashTable 使用synchronized锁HashTable对象,线程安全.

5. HashTable 和 ConcurrentHashMap的区别

HashTable是早期提供的,
在jdk1.7 ConcurrentHashMap 采用的是锁分段技术, 把若干个哈希桶分成一个段, 针对每个段分别加锁.
在jdk1.8, 取消了分段锁, 直接给每个哈希桶分配了一个锁.
相比于HashTable, HashTable只有一个锁. 效率较低.

6. Hash的几种遍历方式

这里不推荐使用keySet的方式, 因为遍历是遍历两遍, 第一遍遍历key, 第二遍获取value使用map.get(key). 效率比较低.

1. 迭代器(Iterator)方式遍历
① 使用迭代器EntrySet的方法进行遍历

Map<Integer,String> map = new HashMap<>();
        map.put(1,"Java");
        map.put(2,"MySQL");
        map.put(3,"SpringBoot");
        Iterator<Map.Entry<Integer,String>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()) {
            Map.Entry<Integer,String> entry = iterator.next();
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }

② 使用迭代器KeySet的方法进行遍历

Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            Integer key = iterator.next();
            System.out.println(key);
            System.out.println(map.get(key));
        }

2. For Each 方式遍历
① 使用For Each的EntrySet方式遍历

for(Map.Entry<Integer,String> entry : map.entrySet()) {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }

② 使用For Each的KeySet方式遍历

for (Integer key : map.keySet()) {
            System.out.println(key);
            System.out.println(map.get(key));
        }

3. Lambda 表达式遍历

map.forEach((key,value)->{
            System.out.println(key+" "+value);
        });

4. Streams API 遍历

// 单线程
        map.entrySet().stream().forEach((entry) -> {
            System.out.print(entry.getKey());
            System.out.print(entry.getValue());
        });
        // 多线程
        map.entrySet().parallelStream().forEach((entry) -> {
            System.out.print(entry.getKey());
            System.out.print(entry.getValue());
        });

7. Set 如何保证不重复

首先调用 hashCode() 方法获取对象的哈希值, 根据对象的哈希值计算对象的存储位置, 判断当前位置是否有元素.
如果当前位置没有元素, 直接将元素存储到该位置
如果当前位置有元素, 就将该位置的所有元素, 和新存入的元素比较是否有哈希值相同的.
如果当前哈希值不同, 直接将元素存储到该位置.
如果当前哈希值相同, 就调用equals()方法, 比较对象内容是否相等.
如果对象内容相等, 就表示有相同元素, 就不存储了.
如果对象内容不相等, 就表示没有相同元素, 返回false, 将元素存储到该位置.

哈希表相关知识