哈希表

作者: 顶儿响叮当 | 来源:发表于2016-03-14 20:41 被阅读133次

今天做华硕的笔试题时,有道题是介绍哈希表和实现它的几个算法,虽然以前查过相关知识,但只是大概理解。

哈希表的概念

哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。

散列存储的基本思路

以数据中每个元素的关键字K为自变量,通过散列函数H(k)计算出函数值,以该函数值作为一块连续存储空间的的单元地址,将该元素存储到函数值对应的单元中。

哈希表查找的时间复杂度

哈希表存储的是键值对,其查找的时间复杂度与元素数量多少无关,哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元素的,因此,哈希表查找的时间复杂度为O(1)。

哈希函数的构造方法

哈希函数的构造方法:
1、直接定址法。取关键字或关键字的某个线性函数值为哈希地址。
即:H(key)=key或H(key)a*key+b
由于直接定址所得地址集合和关键字集合的大小相同,因此,对于不同的关键字不会发生冲突。但是,实际中使用这种方法的情况很少,因为随着关键字的增多,哈希表会变得很庞大。

2、平方去中位法。
取关键字平方后的中间几位为哈希地址。取的位数由表长决定。

3、还有折叠法、数字分析法、除留余数法、随机数法等

处理冲突的方法
1、开放定址法
2、链地址法


参考原文:
http://panlianghui-126-com.iteye.com/blog/968057
http://blog.csdn.net/chenhuajie123/article/details/9210529

相关文章

  • Java数据结构_哈希表_基本概念

    本文目标 哈希表的基本概念,哈希冲突,哈希函数 什么是哈希表 哈希表也叫做散列表(hash有剁碎的意思)哈希表是空...

  • redis数据结构--字典

    Redis的字典底层就是哈希表。 哈希表 首先给出哈希表的定义: 其中可以看到,table是一个哈希表节点的数组,...

  • 哈希表和链表

    优秀文章:Chapter: 散列表(哈希表) 一、哈希表 哈希表hashtable(key,value) 就是把K...

  • 算法-哈希表算法总结

    1 哈希表模拟 思路:通过设计哈希表,模拟O(1)时间复杂度的哈希表。 2 数组作为哈希表 思路:数组就是简单的哈...

  • 数据结构 -- 哈希表及其应用

    这篇主要用来记录一下学习到的关于哈希表的知识点。 文章结构 哈希表 哈希表的定义 哈希表的优缺点 哈希碰撞 负载因...

  • 数据结构与算法(第一季):哈希表(Hash Table)

    一、哈希表(Hash Table) 1、概念 哈希表也叫做散列表。 哈希表的原理: 利用哈希函数生成key对应的i...

  • 深入理解哈希表

    深入理解哈希表 深入理解哈希表

  • 2019 算法面试相关(leetcode)--哈希表

    哈希表相关的原理可以参考下:浅谈哈希表(HashTable)深入理解哈希表哈希表的理解理解HashSet及使用 哈...

  • Redis中的字典

    Redis中的字典 Redis中的字典使用哈希表作为底层实现,一个哈希表中可以有多个哈希表结点,而每个哈希表结点保...

  • Redis数据结构与对象——哈希

    1 字典的实现 Redis的字典使用哈希表作为底层实现,一个哈希表可以有多个哈希表节点,即每个哈希表节点就保存了字...

网友评论

      本文标题:哈希表

      本文链接:https://www.haomeiwen.com/subject/uciflttx.html