开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> hash散列表、hashMap存、取 -> 正文阅读

[数据结构与算法]hash散列表、hashMap存、取

散列表

hash 翻译散列哈希(音译)

什么是散列表
即：散列表/桶是一个数组

散列表（Hash table，也叫哈希表），
是根据关键码值(Key)而直接进行访问的数据结构。
也就是说，它通过把关键码值（key）映射到表（桶，就是数组）中一个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。
（散列函数就是 先得到hashCode值，然后经过一些列运算得到下标值）

给定表M（就是那个桶/数组），存在函数f(key)，对任意给定的关键字值key，
代入函数后若能得到包含该关键字的记录在表中的地址，
则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

即：什么是哈希表？
        就是那个桶，比如hashMap 的存 和 取
    什么是哈希函数？
        比如hashMap就是hash函数，存取的过程自述

散列表(HashMap)的数据结构原理

hashMap的底层是数组实现的

hashMap如何存元素

1、根据元素key调用hachCode方法得到code码值（是个整数）
2、拿到code码值根据 散列函数 得到一个下标
3、如果下标里面没有值就会将数据放到散列表里
4、如果有值：
    两个key进行equals比较、 
    key相等做替换操作?
    key不相等生成链表结构

即：
不同的key经过算法生成的 下标 可能是 一样的，
（散列表/桶 一个下标 保存一个元素）
如果该散列表处有元素，那么就拿两个key进行equals比较，
用来判断二者是否是同一个对象，如果key的equals相等，
那么就认为是同一个对象，则为直接修改替换value

如果相同，就会生成链表结构，
以后再有的元素 经过算法下标还相等，就会挨个比
注意：JDK1.8以后 链表的数据是加到后边的
（产生链表后查询效率就会降低JDK1.8以后，链表>=8，生成红黑树解决）


如何产生链表结构的：
注意：因为后序可能会产生链表结构
所以桶位保存的其实就是头节点值，如果后面产生链表，或者在头节点前产生链表
那么在这个对象里边添加引用 next 或者 pre指向就可以了（前驱和后继）

比对后，发现key和链表的key都不相同， 则会继续链起来

HashMap是查找性能最高的数据结构?

hashMap如何查（取）元素

根据key调用hashCode方法，得到code码值
code码经过散列函数 得到散列表的下标值，
根据下标去散列表直接找到值

注意：相同的key调用hashCode 生成的code值一定是一样的，所以它查询才快

即：hashMap code值经过算找到下标，直接去数组里找到值，
而数组是根据下标查找的，它的速度是最快的，所以hashMap是查询效率最高的

hashMap生成链表会降低查询效率

从JDK1.8开始，
hashMap中若链表的长度值>=8，此时会转换为红黑树
（即：由单向链表转为红黑树，红黑树的查询速度高，一次查找一半）

hashMap JDK1.8前和1.8后的区别

JDK1.8以后
1、hashMap中若链表的长度值>=8，此时会转换为红黑树 （树转化的阈值是8）
2、如果向某个散列表位添加元素，产生链表，那么新添加的元素，是添加在链表的尾部的


JDK1.8以前
1、hashMap 产生的链表 是单向链表
2、如果向某个散列表位添加元素，产生链表，那么新添加的元素，是添加在链表的头部的

散列表存放取元素的原理:?

注意：散列函数严格意义来说是包含获取hashCode值的

hashMap中要尽可能的减少链表的长度,如何实现?

实际上，我们用的hashMap，它的链表长度都保持在2 或 3

如何实现？
当表（桶）中的元素数量超过负载因子对应的值（4/3=0.75）,表进行扩容(2倍)?
3*4=12是临界点，如果超过12 到了13就会扩容，哪怕有链表，因为是元素（链表的数据也是元素）

即：如果散链表的长度是16，当我们来了13个元素，就会自动进行扩容
哈希表的默认长度是16，下标是15

比如我存了12个元素，表（桶/数组）的长度默认是16：
负载因子 = 保存元素数量(12)/数组的长度（16）
默认的负载因子为0.75 就是4分之3

hashMap有两个常量 一个是阈值8，一个是负载因子0.75


hashMap的阈（通：域）值，默认是8，当我们知道要保存的数据量，可以自定义，避免中间扩容这一步操作
如果不知道数量，那就不要给初始容量，可能空间浪费，因为数组是连续的，一旦创建，是不可变得


扩容2倍：
16->32->64>128

细节注意点:

HashMap的 初始容量 和 负载因子 均是可以自定义的
- 通过构造方法可以自定义修改
2^n：....32、16、8、4、2、1 别的都不是

hashMap的初始容量自定义的值若不是2^n,此时初始容量是否为给定的值？
答案：不是

HashMap的初始容量一定是2^n,若自定义给出的值x不是2^n,则容量为大于x最小的2^n
- 例如：
  - 若给定18，他不是2^n? ?那么此时初始容量为32
  - 若给定40，他不是2^n，那么此时初始容量为64

关于HashMap添加的三个关注点?

/**
 * 三个关注点.
 * 1、不同的hashCode码值，产生的下标有可能是一样的
 * 2、扩容 素超过负载因子即扩容
 *      13个元素>12负载因子  map 的table长度（散列表）就会变成扩容 从16 到32
 *      注意：是元素的值，包括链表的
 * 3、HashMap扩容后元素会重新散列 -- 通过Debug观察
 */

如图断点观察，如果map看不见，就右键-view as-Object 当做对象去查看属性

1、hashCode值不同，但是下标可能相同，产生链表?

如下图，table是hash表的长度，默认是16
4 是该元素存入数组的下标?
观察可以发现，Sally和King的hashCode值不同，但是产生的下标都是4，由此生成链表

?新增12个元素后的断点如下

2、扩容

新增第13个后
如下图，元素显示12个，实际size是13个，说明有链表里有一个
而表值变成了32，说明添加的元素超过了负载因子，即扩容

HashMap中数组中保存的元素类型是Node类型--可通过Debug观察
而键值对在java里保存的是Entry类型Map.Entry(key, value);
- 即：java 是通过Entry类型来保存键值对的
  - 而hashMap 的table（数组）里边绝对不是Entry类型
    - 它得保存hash值，key，value，next
  - 它是后来自己了一个类Node来保存的（就像我们写二叉树，自己定义的Node内部类一样）

3、HashMap扩容后元素会重新散列 -- 通过Debug观察

即：当我们长度改变，肯定要重新计算hash值（数组是定长不变的，扩容肯定会生成新的数组）
扩容前Sally的下标是4
扩容后Sally的下标是20

HashMap中产生链表的原因:

1. 不同的对象调用hashcode()可能生成相同的整数,此时产生的下标相同,产生链表
2. 不同的对象调用散列函数可能生成相同的下标,此时不同的对象保存在同一位置,产生链表

hashcode()与equals()

实体类里重写equals方法那么必然重写hashcode方法
重写equals方法的作用：是用来比较对象是否相等的?
- 即：如果有两个对象，判断是否是同一个学生，只要比较学号就可以了，
  - 那么用equals方法是用来比较值的，而不是比较地址，就可以实现
创建两个对象stu1和stu2
stu2是用来修改stu1对象的名字的；即：将tom修改未jack
两个对象的id 都是1001
如何判断这两个对象相等？
- 必须重写equals方法，来比较两个对象的id值，而不是比较两个对象的地址
stu1存入数组的时候，经过散列算法获取下标 4 存入，
那么stu2存入的时候如何确定它的下标也是4？
文档规定：如果根据equals()方法，两个对象相等，那么这两个对象生成的hashcode值必然相等，也就是说，如果想让两个对象的hashcode值相等，那么必然要重写equals方法
hashcode值相同了，获取下标也就相同了，然后key相等，value直接替换，这样就修改了

比如用户注册，如果不重写equals方法，命名两个用户注册信息一样，但是地址不一样，这样逻辑就发生了错误?

hashcode()
- 不同的对象调用hashcode(),可能生成相同的int
- 但是,相同的对象多次调用hashcode().生成的int一定相同 --- hashcode的稳定性
- 若2个对象的equals比较结果为true,则2个对象调用hashcode()必然生成相同的整数


问题：
若2个对象调用hashcode()生成的数值相同,2个对象equals比较结果一定为true吗?
答案：不一定，
即：x,y两个对象调用hashCode生成的整数大部分不相同，极少部分可能相同

如果两个对象的equals比较结果为true 那么生成的hashCode值必然相等

同一个对象调用多次hashCode 一定是稳定的，是相同的


面试题2、
如果两个对象使用equals方法比较后,返回true,则两个对象分别调用hashcode()返回的散列码是一定相等的吗?
答案：一定

HashMap,HashTable,ConcurrentHashMap的区别

HashMap与HashTable的区别:?

1. HashTable是线程安全的,
   HashMap是非线程安全的,
   HashTable为了保证多线程并发时线程安全,给整个table加锁(写,读)--synchronized
2. HashMap中的key可以为null,HashTable中的key不允许为null

Collections.synchronizedMap(HashMap)
- 原理:依然是给table加锁 - synchronized
ConcurrentHashMap -- JUC java.util.concurrent.
- 替代了HashTable,concurrentHashMap也是线程安全的.(从数据结构上进行了优化)
- 数据结构:Sengment (区,段)
volatile 线程安全中,修饰成员,保证数据的可见性

Hashmap与ConcurrentHashMap的区别,
1. HashMap是非线程安全的,而ConcurrentHashmap是线程安全的
2. HashMap在1.8之前采用的数组+链表的数据结构,
1.8之后采用的数组+链表+红黑树的数据结构;
ConcurrentHashMap在1.8之前数据结构中有segment,segment中保存n个桶,
存取元素时,需要经过两次hash算法,
第一次计算出元素位于segment中的下标,
第二次计算出元素在segment中数组的下标,
通过给segment加锁保证线程安全,就可以实现多个线程并发执行

?写出对map进行遍历的代码实现.

map.forEach((k,v)-> System.out.println(k+"-"+v));
        //增强for循环实现
//        for (Map.Entry<String,Integer> entry: map.entrySet()) {
//            System.out.println(entry.getKey());
//            System.out.println(entry.getValue());
//
//        }
        //遍历map中所有的key并输出 -- keySet():Set<K>
        for (String str: map.keySet()) {
            System.out.println(str);
        }
    }