`
暗夜魅影
  • 浏览: 21362 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

Hash的初级理解

 
阅读更多

     以前大家在接触框架结构的时候都接触过Hashmap,对于hash相信很早的时候大家都有一定的接 触,但是那时候我们对于hash的理解似乎只局限于名字和他的一些我们应用时的方面。

      在接触之前对于hash我一直都是觉得很困惑的东西,一直以为hash是一种很复杂的计算,或者那时候以为是一种和特别的属性,因为最先接触也是理解的就是hashcode,唯一标示,曾经因为这个以为所谓的hash就是与事物特性有关的一些方法,因为现在接触了并且应用的就是hashset所以谈一下通过hashset对于hash 的理解吧

     在我们平时用到的set结合中就是简单吧我们要添加的数据加入到set集合中,对于自己实现的set我们可以用数组也可以用链表来实现,对于数组和链表之间的差别和适合的应用环境大家都应该已经清楚了,通常对于少数数据的情况下不管对于数组还是链表我们所用的时间都是很少的,并没有太大的优劣性,但是如果对于较大的数据量进行操作的时候我们应该采取什么样的方法来实现呢?

 

      假设现在又一个很大的数据量的数据要我们对其进行各种操作,当然这种也分情形

  1、若数据量固定我们只需要查找里面的信息,这种情况下仅仅数组就相对于简单的多

  2、如果我们只是对里面的数据进行插入删除,这种情况下仅仅用链表来实现就简单的多了

   以上两种情况是两种极端的情况

   问题是:因为大多时候我们对于数据可能要同时有着两种操作,就是既要查找又要插入删除,但是基于我们的理解查找的话用数组实现是最简单的,而对于插入删除我们会悠闲选择链表实现;

   解决这个问题大多人都会想到我们把数组和链表结合,链表跟数组的结合有两种方式

     一、数组实现的链表;

     二、链表实现的数组;、

       第一种就是把数组作为链表的没一个节点这种方面最大的好处就是继承了链表的特点:内存的存储是离散的,它不需要连续大量的内存,但是因为数组开始的时候就被分配了固定的内存其实需要的空间并没有节省,这样我们字对其进行操作的时候就会有可能有大量的内存空间的浪费。 

       第二种方法是整体上还是数组的特性,查找速度快,而数组的每一个元素是链表组成,这样实现的好处很明显,如果我们在未知数据的情况下,不断地加入,对于内存的申请是通过我们加入数据的增加而增加的,因为数组的没一个元素是链表,所以整个数据在内存中的存储其实还是表“离散”的特征。我们对于内存的浪费就会大大减少。

      所以比较来看 我们对于新的又数组和链表的结合方式应该选择第二种,现在要考虑的是怎么结合?

     明显我们要用数组和链表结合的方式从结构上可以看出其实相当于“分组“存储,没一个数组的元素相当于一组的属性,而里面的链表相当于存储的具有相同的属性的数据。这样我们在选择同一个数组元素里链表数据分配的时候就要有一个分组的标准,例如:如果要存储的是一个学校学生的数据,我们就可以按照院系来存储,也就是每个数组元素代表的属性就是一个院系,里面的链表中的数据就是这个院系的学生。

      这样按照这种思路基本上的hash 我们已经理解里面的结构,或者说我们都基本有一个自己的hash的定义了,但是同时在存储数据的时候我们还要注意的是因为我们使用链表实现的数组,我们这么做主要就是为了既方便于数据的查找也方便与数据的插入和删除,但是在我们存放数据的时候根据不同的分组方式会不会有问题出现呢?例如:

     我们现在要存入的是十万个int 的数据,而我们分组是根据与数组长度取余来分组,这样就有可能会产生:

          1、 一种情况刚好所有的数据取余后的结构都是一样的,这样我们构建的自己的hash就会出现数组中只有一个元素的链表不为空,而其他的元素都为空,这样我们构建的就纯属是一个链表,就丢失了数组查找方便的特性。

           2、另一种就是刚好数据取余后的结果都是不同的,这样没一个数组的元素中的链表就有可能都只有一个元素,这样就会变成一个纯数组,就失去了链表插入删除方便的属性。

     这个问题怎么解决呢?

     我们需要的是数组中的链表都是均匀的,这样才能兼顾数组和链表的特性。要解决这个问题主要有两个方面

     一、合理的选取分组方式,合理的分组方式是很重要的,如果一种合理的分组方式能够刚好符合数据的处理,这样我们在数据的添加是就会省去很多麻烦,减少很多rehash(后面会说到),大大缩减了处理时间,提到了效率;

     二、当我们找不到很好的能够适应数据分组方式的时候,判断如果有可能会出现以上两种极端 的情况下我们就要进行rehash(就是指要重新建立hash表),rehash我们一般采取的就是增加数组的长度,这样在对分组我们可以进行更详细,或者分散在同一属性聚集的数据。这里对于数组长度的增加也要合理的选取,这也是跟hash效率有关的很重要的一个方面,就以我实现的方法举例吧

       "对于一个大量的数据进行于数组长度的取余分组"

     这个我们判断在数据位置的情况下还是很有可能出现极端情况的,而其中的rehash如果我们选取的是每次增加数组长度的一半,这样在我们rehahs 的时候因为我们要吧原来hash 中的数据重新加入到新的hash 中,我们就需要遍历以前的hash然后逐个元素加入;而另一种我们采取的就是直接数组翻倍,这样的好处就是因为是取余,如果只是数组防备我们就可以直接复制数组中的链表。而链表在新数组中的位置就是原来的位置加上数组长度!这种方法就大大减少了遍历数据的时间和重新计算分组的时间,当然这种方法也是有缺点的,对于未知的数据,如果我们每次都是数组翻倍,很有可能我们翻倍后在需要加入的只有一个数据了,这样的话我们就会大大浪费空间内存,如果从内存来看的话这种方法就不如第一种了。当然对于追求效率还是内存要我们可以根据需要采取不同的rehash方式。

        

      因为对于一种新事物的理解我们是要建立在不断地应用不断地体会中,所以对于hash 的理解也就局限于这些吧,因为毕竟刚刚接触,其他的看的都是一些实现 的方法,对于里面的具体的实现还是看源代码理解会更深一些。

 




 

 

 

 

 

 

分享到:
评论

相关推荐

    Hash表

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

    Java初级面试题.7z

    理解其数据结构(如String、Hash、List、Set、Sorted Set)及操作命令。 4. **分布式相关**(9_分布式相关.pdf): - 分布式系统概念,CAP理论,分布式锁,分布式服务发现,负载均衡等。 - 可能会涉及的开源框架...

    redis初级入门笔记

    以上就是 Redis 初级入门的一些关键知识点,理解并掌握这些内容,可以帮助你快速上手 Redis 并应用于实际项目。在实际操作中,你可以通过创建、读取、更新和删除不同数据类型来进一步熟悉 Redis 的功能。同时,不断...

    Redis初级案例(推荐)

    Redis支持多种数据类型,如字符串(String)、哈希(Hash)、列表(List)、集合(Set)和有序集合(Sorted Set)。这些数据类型提供了丰富的操作命令,满足不同场景的需求。例如,字符串是最基本的数据类型,可以用来存储简单...

    PHP 初级

    学习PHP不仅仅是为了掌握这些基础功能,更重要的是理解其背后的原理和技术思想,这样才能更好地应用于实际项目中。随着经验的积累,可以逐渐接触到更多高级特性和技术栈,如面向对象编程、框架使用等。

    redis 初级 + 高级 讲解笔记

    3. **数据类型**:除了基础的字符串,Redis 还提供哈希(Hash)、列表(List)、集合(Set)和有序集合(Sorted Set)。例如,哈希可以存储键值对的集合,列表可以进行基于索引的插入和删除,有序集合则支持按分数...

    ruby初级中文教程与实例

    本教程专为初学者设计,旨在帮助你快速掌握Ruby的基础知识,并通过丰富的实例加深理解。 一、Ruby基础 1. 变量:Ruby中的变量分为五种类型:局部变量(以小写字母或下划线开头)、实例变量(以`@`开头)、类变量...

    网络与信息安全(初级)模拟试卷

    【网络与信息安全(初级)模拟试卷】是一份针对全国医疗卫生信息技术职业技能培训与认证考试的练习题目,涵盖了网络和信息安全的基础知识。试题涉及了OSI网络七层协议模型、访问控制策略、入侵检测技术、TCP/IP协议...

    mysql面试题从初级到高级都有

    面试中,从初级到高级的知识点涵盖了对数据库基础的理解、操作技能、性能优化和高级特性的掌握。 1. **MySQL 基础**: - MySQL 是一个开源的 SQL 数据库,支持多种操作系统,提供了丰富的功能和良好的可扩展性。 ...

    【MySQL技术资料】-(机构内训资料)MySQL优化学习思维笔记

    理解B-Tree、Hash和Full-text等不同类型的索引,以及如何选择合适的索引策略至关重要。注意避免索引滥用,以及创建复合索引来覆盖更广泛的查询需求。 2. **查询优化**:学习如何编写高效的SQL语句,避免全表扫描,...

    数据库系统工程师考试大纲

    - 常用数据结构:如数组、链表、栈、队列、树、图、集合和Hash表的定义、存储方式和操作。 - 常用算法:涵盖排序、查找、数值计算、字符串处理等,强调算法效率、设计和复杂性分析。 3. 软件知识: - 操作系统:...

    hashmyfiles【32&64;&中文包】.zip

    常见的哈希算法有MD5(Message-Digest Algorithm 5)、SHA-1(Secure Hash Algorithm 1)和SHA-256等。HashMyFiles便是一款基于这些算法的实用工具,它能快速地为每个选定的文件生成这些哈希值。 使用HashMyFiles,...

    MySQL性能调优与架构设计

    2. 索引优化:索引是提升查询速度的关键,书里会讲解不同类型的索引(如B-TREE、HASH、RTREE等)及其应用场景,以及如何创建和维护索引以达到最佳性能。 3. 内存管理:MySQL的缓冲池、排序区、临时表等内存结构对...

    php简单企业网站管理系统

    8. **模板引擎**:尽管是初级项目,但可能已经引入了简单的模板引擎,将业务逻辑与视图展示分离,使代码更易于维护。 9. **性能优化**:可能涉及缓存技术,如使用PHP的`APC`或`memcached`,来提高页面加载速度和...

    高性能 MySQL 第3版

    总的来说,《高性能 MySQL 第3版》是一本全面覆盖 MySQL 高级特性和最佳实践的指南,无论你是初级开发者还是经验丰富的 DBA,都能从中获得宝贵的洞见和技能,以提升你的 MySQL 系统的性能和稳定性。通过阅读这本书,...

    MySQL面试题大全(吊打面试官).rar

    - 索引的创建与优化:B-TREE、HASH、全文索引等,以及索引的选择和避免索引失效的策略。 - 数据库事务:ACID属性,事务的隔离级别及其影响。 - 视图的概念及用途,视图的优点和限制。 4. 触发器与存储过程 - ...

    MySQL性能调优与架构设计-简朝阳

    索引策略是提高查询速度的关键,书中的内容可能涉及BTree、Hash、Full-text等各种类型的索引,以及如何根据业务需求创建合适的数据结构。存储引擎的选择,如InnoDB和MyISAM各有优劣,了解它们的特性有助于优化事务...

    leetcode跳跃-interview:DevOps,SRE,分布式领域

    理解] 中级 高级 4. 分布式 Raft Gossip Hash算法 Lease 租约机制 5. 数据库 6. 发布系统 发布策略 滚动更新 蓝绿发布 金丝雀发布 / 灰度发布 CI/CD 制品库 7. SRE 2. 混沌工程 2. 数据结构和算法 1. 语法 双端队列 ...

    信息奥赛noi、CSP-J/S算法课件.zip

    CSP-J/S是中国计算机学会举办的信息技术能力认证,分为初级(CSP-J)和中级(CSP-S),主要考察学生的算法设计和编程能力。 1. **位运算**:在计算机科学中,位运算是对二进制数进行的操作,如与(AND)、或(OR)...

    二OO八年一月GDCA培训

    - **哈希运算**(Hash)将任意长度的输入转化为固定长度的输出,微小的变化会导致哈希值显著不同,用于验证数据完整性。 3. **数字证书的基本结构** - **数字证书**是由权威机构(如GDCA,广东省数字证书认证中心...

Global site tag (gtag.js) - Google Analytics