HashMap的一些面试点

喜欢ヅ旅行 2022-12-09 04:55 90阅读 0赞

# 数据结构 #

数组+链表

**·tip：**当某一个key长度超过8，则链表转化成红黑树存储。

# Hash算法优化 #

static final int hash(Object key){
        int h;
        return if(key==null)?0:(h=key.hashCode())^(h>>>16)
    }

【优化】对每个hash值，让高低十六位进行了异或运算，让它的低16位同时保持高低16位的特征，尽量避免一些hash值后续出现冲突，出现在同一个位置上。

eg:

1111  1111  1111  1111 1111 1010  0111 1100 ->(原hash值,没有优化的hash值)

0000 0000 0000 0000 1111 1111  1111  1111 ->(原hash值，右移16位)

1111  1111  1111 1111 0000 0101 1000  0011 ->(原hash值，同右移16位后，进行异或运算)

**·tip： **与运算（逻辑乘），对应位全是1结果为1，否则为0；或运算（逻辑加），对应位全是0结果为0，否则为1；

异或运算，参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为 0。

寻址算法优化：（n-1）& hash

【优化】用与运算替代取模，提升性能

假如n=16，n是数组长度

0000 0000 0000 0000 0000 0000 0000 1111 ->(n-1)

1111  1111  1111 1111  0000 0101 1000  0011 ->(异或后的hash)

0000 0000 0000 0000 0000 0000 0000  0011 ->(&结果)

# 如何解决hash碰撞问题 #

数组的一个位置存在多个值，就会变成一个**链表**，这个链表是**红黑树**结构；

时间复杂度由O(n)->O(logn)；

# HashMap是如何进行扩容 #

底层是一个数组，当数组满了以后就会自动进行扩容，变成一个更大的数组。

数组长度=16；

eg1：

n-1    :   0000 0000 0000 0000 0000 0000 0000 1111

hash1:  1111  1111  1111  1111  0000 1111 0000 0101

&结果：0000 0000 0000 0000 0000 0000 0000 0101 =5（index=5的位置）

eg2：

n-1    :   0000 0000 0000 0000 0000 0000 0000 1111

hash2:  1111  1111  1111  1111  0000 1111 0001 0101

&结果：0000 0000 0000 0000 0000 0000 0000 0101 =5（index=5的位置）

数组长度为16的时候，他们俩个的hash值的位置是一样的，用链表来处理，出现一个hash冲突问题。

如果数组的长度扩容成32位，重新对每个hash值进行寻址，也就是每个hash值跟新数组的length-1进行与操作。

eg1：

n-1    :   0000 0000 0000 0000 0000 0000 0001 1111

hash1:  1111  1111  1111  1111  0000 1111 0000 0101

&结果：0000 0000 0000 0000 0000 0000 0000 0101 =5（index=5的位置）

eg2：

n-1    :   0000 0000 0000 0000 0000 0000 0001 1111

hash2:  1111  1111  1111  1111  0000 1111 0001 0101

&结果：0000 0000 0000 0000 0000 0000 0001 0101 =21（index=21的位置）

发表评论取消回复

表情：

评论列表（有 0 条评论，90人围观）

还没有评论，来说两句吧...

相关阅读

相关 Hashmap知识点

目录 1.未被重写的hashCode() 和equal()方法 2.在HashMap中，判断两个对象(key)是否相等的规则: 3.为什么要重写equal方法？ 4.为

骑猪看日落/ 2024年03月29日 14:47/ 0 赞/ 76 阅读

相关 HashMap的面试题

HashMap的特性 1.HashMap存储键值对实现快速存取，允许为null。key值不可重复，若key值重复则覆盖。 2.非同步，线程不安全。 3.底层是has

傷城~/ 2023年07月06日 05:00/ 0 赞/ 25 阅读

相关 HashMap源码及面试知识点

（1）HashMap 的原理，内部数据结构？数组+ 链表（或1.8红黑树）验证：数组+ 链表以Node数组的形式存储 transient Nod

淩亂°似流年/ 2023年07月02日 03:16/ 0 赞/ 44 阅读

相关 HashMap的一些面试点

数据结构数组+链表 ·tip：当某一个key长度超过8，则链表转化成红黑树存储。 Hash算法优化 static final int hash(Obj

喜欢ヅ旅行/ 2022年12月09日 04:55/ 0 赞/ 91 阅读

相关哈希、HashMap原理及源码、Hash的一些应用面试题

一、哈希定义 Hash，一般翻译做“散列”，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出

喜欢ヅ旅行/ 2022年08月04日 01:41/ 0 赞/ 183 阅读

相关 java集合-HashMap的一些记录

参考链接： http://www.importnew.com/10620.html http://www.importnew.com/18633.html 1、HashM

拼搏现实的明天。/ 2022年05月31日 11:39/ 0 赞/ 199 阅读

相关 Linux的一些点

1.如何查找一个进程打开的所有文件只查看该进程：ps -ef | grep pid 查看该进程打开的文件：lsof -p pid 查看内存分配：lcat /proc/p

一时失言乱红尘/ 2021年12月13日 02:27/ 0 赞/ 205 阅读

相关 HashMap--concurrentHashMap的一些知识搜集

目录 HashMap ConCurrentHashMap -------------------- 面试中经常会被问道： > 面试官：有了解HashMap吗，讲一下H

痛定思痛。/ 2021年12月12日 12:51/ 0 赞/ 285 阅读

相关 Java面试知识点（一）（补充）hashmap深度理解

1、hashmap 的数据结构要知道 hashmap 是什么，首先要搞清楚它的数据结构，在 java 编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（

偏执的太偏执、/ 2021年09月29日 08:46/ 0 赞/ 270 阅读

相关 Java面试知识点（一）hashmap、hashtable和hashset

1. 关于 HashMap 的一些说法： a) HashMap 实际上是一个 “链表散列” 的数据结构，即数组和链表的结合体。HashMap 的底层结构是一个数组，数组中

红太狼/ 2021年09月23日 00:28/ 0 赞/ 281 阅读