`

HASH表原理

    博客分类:
  • JAVA
阅读更多

   今天由于天气不好,整天就闷在家里无所事事,偶然间想起前段时间与一个朋友讨论的问题,就是关于哈希函数以及哈希表使用上的,而他对哈希表的理解却是一塌糊涂,当时由于比较忙,也没有仔细与他具体讨论此问题,趁今天有空就想将关于哈希表的概念简单的写一下,其实我知道虽然很多朋友在开发的过程中经常使用哈希表,但是实际上对于哈希表原理理解的应该很少,希望在此能让各位朋友对哈希表有所了解。

    言归正传,哈希表又名散列表,其主要目的是用于解决数据的快速定位问题。考虑如下一个场景。
   
    一列键值对数据,存储在一个table中,如何通过数据的关键字快速查找相应值呢?不要告诉我一个个拿出来比较key啊,呵呵。

    大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。

    具体如何做呢?大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。

    不知道说到这里,一些不了解的朋友是否大概了解了哈希表的原理,其实就是通过空间换取时间的做法。到这里,可能有的朋友就会问,哈希函数对key进行转换,取余的值一定是唯一的吗?这个当然不能保证,主要是由于hashcode会对数组长度进行取余,因此其结果由于数组长度的限制必然会出现重复,所以就会有“冲突”这一问题,至于解决冲突的办法其实有很多种,比如重复散列的方式,大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数,既 (h(k)+i) mod S , i=1,2,3…… ,直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。

    不知道写的这些是否足够清楚,如果还有不明白的欢迎各位朋友提出意见,谢谢!

 

 

 

 

评论:

 

     hash出来得值的重复是不可避免的,而如果加上key的话,确实是唯一的,事实上java的算法就是使用你说的那种方法,将相同hash值的value放到同一个桶里,再通过key进行区分,这种方式只能说是解决冲突的一种方法,而非是一定的,而我上面举的重复散列也是其中一种,所以我在后面就说了,还有很多种解决冲突的方式。

 

 

不同对象有不同的hashcode,但不同的hashCode经过与长度的取余,就很可能产生相同的index,这个才是hash算法的真正冲突,冲突时不可避免的,hashCode超出了int的范围也是一种,不过一般不考虑。当几个对象产生了俄相同的index时候,解冲突就是把这个index的位置放置的是一个链表,再通过hashcode和key取得对于的数据

分享到:
评论

相关推荐

    hash join 原理和算法

    **二、Hash Join原理** 在实际操作中,Oracle使用哈希函数对连接键进行运算,将数据分到不同的分区。例如,通过求余函数(Mod(join_column_value,10))将数据分到10个分区。这样,只需处理匹配的分区对,减少不必要...

    GeoHash核心原理解析

    GeoHash是一种将地理坐标(主要是经纬度)转换为一种特定格式字符串的技术,该字符串可以代表一个地理坐标所在的区域,并能够方便地用于地理位置相关的数据处理,例如地理位置索引、空间查询等。GeoHash的字符串长度...

    Hash表的分析以及组成原理解析及代码实现.md

    Hash表采用了数组加链表的结构,即一个数组元组中不再是存储单个元素,而是存储一个链表,就好比包租婆收租的时候,一个握把上面挂了一连串的钥匙一样。Hash表的引出是为了减少查询数据库操作所带来的时间问题,将...

    java 散列表原理

    就是java的散列表示意图 很清晰易懂 比枯燥额文字好多了

    hash join算法原理

    二、Hash Join 原理 在实际操作中,Hash Join假设连接键上的数据分布是均匀的,但这并不总是成立。Oracle为此引入了一些优化技术: 1. 位图向量过滤:在构建Hash Table时,Oracle记录连接键的唯一值,形成位图向量...

    Hash表模板类

    在"hash表模板类"这个压缩包中,你可能找到了一个实现了以上功能的C++源文件。通过阅读和理解代码,你可以学习到自定义哈希表的实现细节。此外,附带的测试代码和可运行文件可以帮助你验证该哈希表模板类的正确性,...

    数据结构 hash表 hash table 原理,以及实现介绍

    hash 表是我们经常使用的一种存储数据的结构,它查找性能不会因为数据的增长而下降。

    一致性Hash算法的原理及实现

    ### 一致性Hash算法的原理及实现 #### 一、引言 一致性Hash算法是一种用于解决分布式环境下数据存储和检索问题的重要技术。它最初由David Karger等人在1997年的论文《Consistent Hashing and Random Trees: ...

    Hash join算法原理

    相比Nested Loop Join,Hash Join 在处理大规模数据时更具有优势,因为它不需要在驱动表上建立索引。 Hash Join 的工作原理分为两个主要步骤:构建和探测。首先,较小的表(称为 build input 或者 S)被加载到内存...

    双向链表与hash表

    双向链表和哈希表在实际编程中都有着广泛的应用,理解它们的工作原理和使用方式对于提升程序性能和可维护性至关重要。通过学习和实践,开发者可以灵活运用这些数据结构来解决各种复杂问题。在具体实现中,需要考虑...

    c语言hash表源码

    哈希表(Hash Table)是一种数据结构,它通过计算一个关联数组中的索引来确定一个特定元素的存储位置,使得在平均情况下,查找...在实际编程中,根据具体需求,哈希表的实现可能会有所不同,但基本原理和流程是相似的。

    hash表学习基础程序

    `study-hash`这个文件可能是对哈希表学习的代码实现,包括了哈希函数的设计、冲突处理方法的实现,以及可能的一些性能测试。通过阅读和理解这个程序,你可以更深入地掌握哈希表的工作原理和实际运用。在实践中,不断...

    数据结构课程设计(C++)

    数据结构课程设计是计算机科学中一个重要的实践环节,它通常要求学生通过编程实现常见的数据结构,如链表、栈、队列...通过分析和理解这个项目,不仅能加深对Hash表原理的理解,还能提升C++编程和软件工程的实践经验。

    Hash表

    总结文档`hash表.doc`和`hash总结.doc`可能涵盖了哈希表的基本概念、原理、哈希函数的设计、冲突解决策略以及哈希表在实际应用中的案例分析。深入阅读这些文档将有助于进一步理解哈希表的工作机制及其在软件开发中的...

    js单页hash路由原理与应用实战详解.docx

    js单页hash路由原理与应用实战详解.docx

    hash表C语言实现

    下面将详细介绍哈希表的原理以及如何用C语言进行实现。 哈希表的核心思想是通过哈希函数将键(Key)映射到数组的特定位置,使得查找、插入和删除操作的时间复杂度接近O(1)。哈希函数设计的关键在于减少哈希冲突,即...

    hash.rar_HASH算法_fpga hash_hash_zebra85v_哈希表Verilog

    描述中提到“有少量算法介绍”,这可能涵盖了基本的哈希函数原理,比如CRC(Cyclic Redundancy Check)、MD5(Message-Digest Algorithm 5)、SHA(Secure Hash Algorithm)系列等,这些算法在数据完整性验证和身份...

    信息安全原理与技术-第五章Hash函数和数字签名.ppt

    Hash函数和数字签名 Hash函数和数字签名 Hash函数和数字签名

    c语言hash表

    #### 一、Hash表概念与原理 Hash表是一种根据键值(Key value)来直接访问内存存储位置的数据结构。通过一个哈希函数(Hash function),可以将任意长度的键值映射为一个固定长度的数值,这个数值即为索引地址。...

    Hash map 哈希表

    哈希表,也被称为Hash Map,是计算机科学中一种高效的数据结构,用于存储键值对。它通过一种称为哈希函数的过程将键映射到数组的特定位置,从而实现快速的查找、插入和删除操作。在哈希表中,查找时间通常接近常数...

Global site tag (gtag.js) - Google Analytics