你不知道的HashMap

面试中经常会问到常用数据结构,比如HashMap。 相信你平时几乎每天都会用到HashMap,但是你知道它是的实现原理是怎样的吗? 这里先提几个问题:HashMap和Hash算法有什么关系?HashMap中的键值对是以put的次序顺序排列的吗?

HashMap之存储

注意表里有几个信息, · 排列顺序并不是以存储次序来的 · hash 值长度是固定的

面试时要记住这两个关键点,因为说起HashMap的原理基本离不开这个现象。 现在我们来解释其中的原理。

HashMap 存储时会以Hash算法将输入的key值变换为固定长度的输出计算为index, 如果无碰撞则直接放进HashMap, 如果有碰撞则以链表放到对应的index后, 如果碰撞导致链表长度过长,则将链表转换为红黑树, 如果节点已经存在则更新为新值, 如果HashMap满了则resize扩展HashMap。

什么是哈希碰撞呢?

因为Hash算法是将任意长度的输入转换为固定长度的输出,那么就必然会存在Hash值重复的情况。 此时就需要将key作为链表添加到对应的index后了。 当然每个节点包含了Hash,Key,Value信息,当Hash碰撞时还会以Key作为判断依据,所以以链表存储也不会影响数据唯一性。

HashMap的大小怎么确定呢?

HashMap用两个东西来确定大小 · Initial Capacity · Load Factor Capacity是HashMap的buckets数量,也就是节点的数量。Factor则是允许的最大容量比例 当HashMap的存储量超过Factor,则需要对HashMap进行resize,一般是2倍Capacity。

原文发布于微信公众号 - Android每日一讲(gh_f053f29083b9)

原文发表时间:2018-02-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的博客

选择排序

分类: 选择排序(选择排序,堆排序,平滑排序,笛卡尔树排序,锦标赛排序,圈排序) 思想: 1、从左至右遍历,找到最小(大)的元素,然后与第一个元素交换。 2、从...

34080
来自专栏平凡文摘

7大经典的排序算法总结实现

14920
来自专栏菩提树下的杨过

python:函数的高级特性

23330
来自专栏我是攻城师

Java里面关于数组拷贝的几种方式

33240
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版6.7节多继承

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

9310
来自专栏从流域到海域

《笨办法学Python》 第40课手记

《笨办法学Python》 第40课手记 本节课讲述的字典,一种比数组更强大的数据结构,字典(dict)的另一个名称是散列(hash)。 我将在后面具体解释dic...

21670
来自专栏书山有路勤为径

1.C与C++

使用c++中的标准库类型vector可以很轻松的完成任务。 不需要管理内存分配,对不同的类型都可以处理

13840
来自专栏程序员互动联盟

【编程基础】C++比C牛逼的七个点

1. 函数检测增强 ? 在C语言中,重复定义多个同名的全局变量是合法的,在C++中,不允许定义多个同名的全局变量。 C语言中多个同名的全局变量最终会被链接到全局...

36750
来自专栏Android干货

Python面向对象高级编程

Python允许在定义class的时候,定义一个特殊的__slots__变量,来限制该class实例能添加的属性

10320
来自专栏我是攻城师

在Scala里面如何使用正则处理数据

34450

扫码关注云+社区

领取腾讯云代金券