哈希结构是如何找到相对应的键-值对?

简介: 哈希结构作为一种抽象数据结构,Hash表的实现思路如下: 通过某种算法,在 键--值对的存储地址和 键--值对中的key之间,建立一种映射,使得每一个key,都有一个确定的存储地址于之对应。这种算法被封装在Hash函数中。

哈希结构作为一种抽象数据结构,Hash表的实现思路如下:

通过某种算法,在 键--值对的存储地址和 键--值对中的key之间,建立一种映射,使得每一个key,都有一个确定的存储地址于之对应。这种算法被封装在Hash函数中。

在查找时,通过Hash函数,算出和key对应的存储地址,从而找到相应的键-值对。这样就不需要遍历了(付翔注)

相对于通过遍历整个键-值对列表来进行查找,Hash表的查找效率要高得多,理想的情况下算法复杂度仅为o(1)(遍历查找的复杂度为o(n))。Flash内置的哈希结构有Object和Dictionary两种。访问速度上Dictionary要快于Object(参考 Dictionary VS Object VS Array ),并且支持弱引用。Haxe的选择面则更广一些。Dictionary提供了一种泛型结构,并针对key为int型的哈希结构做了特殊优化——IntHash。

目录
打赏
0
0
0
0
13
分享
相关文章
|
4月前
查找数组中最大的元素值
【10月更文挑战第29天】查找数组中最大的元素值。
43 4
什么是可哈希对象,它的哈希值是怎么计算的?
什么是可哈希对象,它的哈希值是怎么计算的?
155 6
字典的 key 是怎么映射成索引的,索引冲突了又该怎么办?
字典的 key 是怎么映射成索引的,索引冲突了又该怎么办?
81 2
【数据结构-哈希表 一】【原地哈希】:缺失的第一个正整数
【数据结构-哈希表 一】【原地哈希】:缺失的第一个正整数
123 0
Redis第五弹-HASH结构相关指令和介绍,计数功能Hash-哈希(Redis本来就是键值对结构,哈希,就相当于键值对嵌套了一个键值对)的多种指令Hset key field value-
Redis第五弹-HASH结构相关指令和介绍,计数功能Hash-哈希(Redis本来就是键值对结构,哈希,就相当于键值对嵌套了一个键值对)的多种指令Hset key field value-
集合、哈希表、字典
集合、哈希表、字典
87 0
【哈希映射】【 哈希集合】 381. O(1) 时间插入、删除和获取随机元素 - 允许重复
【哈希映射】【 哈希集合】 381. O(1) 时间插入、删除和获取随机元素 - 允许重复
两个map中的数据,按照相同键,将所对应的值相加方法
两个map中的数据,按照相同键,将所对应的值相加方法
|
10月前
|
705. 设计哈希集合
705. 设计哈希集合
59 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等