精华内容
下载资源
问答
  • 常用数据结构的应用场景

    千次阅读 2016-05-06 13:43:12
    1、单向链接 单向链表适用于只从一端单向访问的场合,这种场合一般来说: (1)、删除时,只适合删除第一个元素; ...(2)、添加时,只直接添加到...这种典型的应用场合是各类缓冲池和栈的实现。 2、双向链表

    1、单向链接

    单向链表适用于只从一端单向访问的场合,这种场合一般来说:

    (1)、删除时,只适合删除第一个元素;

    (2)、添加时,只直接添加到最后一个元素的后面或者添加到第一个元素的前面;

    (3)、属于单向迭代器,只能从一个方向走到头(只支持前进或后退,取决于实现),查找效率极差。不适合大量查询的场合。

    这种典型的应用场合是各类缓冲池和栈的实现。

    2、双向链表

    双向链表相比单向链表,拥有前向和后向两个指针地址,所以适合以下场合:

    (1)、删除时,可以删除任意元素,而只需要极小的开销;

    (2)、添加时,当知道它的前一个或后一个位置的元素时,只需要极小的开销。

    (3)、属于双向迭代器,可以从头走到尾或从尾走到头,但同样查找时需要遍历,效率与单向链表无改善,不适合大量查询的场合。

    这种典型的应用场景是各种不需要排序的数据列表管理。

    3、数组(含Delphi中动态数组)、列表(Delphi/C++ Builder中的TList)向量(C++中std::vector)

    这种数据结构使用一段连续的空间来存贮元素,所以可以直接通过索引来获取到某个元素,而且可以通过对元素的内容进行排序,然后使用二分法查找,从而提供查找效率。其适合的场合主要是:

    (1)、不会频繁增删元素的场合,因为增删元素都牵涉到元素空间的重新分配,频繁的内存分配操作会大幅降低操作效率。但添加操作时,可以通过预分配足够的空间来优化添加时的效率。

    (2)、属于随机迭代器,可以随机访问任意元素。对于已排序的元素查找起来效率较高。

    4、二叉树(含红黑树、平衡二叉树等)

    这个数据结构类似于双向链表,任意插入元素时都会自动排序,红黑树和平衡二叉树都使二叉树尽量平衡,从而使查询时和二分法类似。它适合的场合主要是:

    (1)、需要时刻保证列表元素的有序排列;

    (2)、需要频繁的增删和查询操作;

    (3)、属于双向迭代器,不能随机访问任意元素;

    5、哈希桶

    这个数据结构使用数组和链表来管理元素,在好的桶尺寸和哈希算法支持下,理想上可以达到接近数组的随机访问效率。其适合的场合主要是:

    (1)、不需要保证元素的顺序(因为它是按哈希值决定插入到那个桶里,与原始数据内容无关);

    (2)、需要频繁的增删和查询操作;

    (3)、属于单向或双向迭代器(取决于具体实现),不能随机访问任意元素。

    展开全文
  • Redis几种数据结构的应用场景

    千次阅读 2017-06-14 17:53:31
    1、String  常用命令:  除了get、set、incr、decr mget等操作外,Redis还提供了下面一些操作:  获取字符串长度  往字符串append内容  ...String是最常用一种数据类型,普通key/value存储都可
    1. 1、String  
    2. 常用命令:  
    3. 除了get、set、incr、decr mget等操作外,Redis还提供了下面一些操作:  
    4. 获取字符串长度  
    5. 往字符串append内容  
    6. 设置和获取字符串的某一段内容  
    7. 设置及获取字符串的某一位(bit)  
    8. 批量设置一系列字符串的内容  
    9.   
    10. 应用场景:  
    11. String是最常用的一种数据类型,普通的key/value存储都可以归为此类,value其实不仅是String,  
    12. 也可以是数字:比如想知道什么时候封锁一个IP地址(访问超过几次)。INCRBY命令让这些变得很容易,通过原子递增保持计数。  
    13.   
    14. 实现方式:  

    1. m,decr等操作时会转成数值型进行计算,此时redisObject的encoding字段为int。  


    hash
    1. 常用命令:  
    2. hget,hset,hgetall 等。  
    3. 应用场景:  
    4. 我们简单举个实例来描述下Hash的应用场景,比如我们要存储一个用户信息对象数据,包含以下信息:  
    5.            用户ID,为查找的key,  
    6.            存储的value用户对象包含姓名name,年龄age,生日birthday 等信息,  
    7.    如果用普通的key/value结构来存储,主要有以下2种存储方式:  
    8.        第一种方式将用户ID作为查找key,把其他信息封装成一个对象以序列化的方式存储,  
    9.            如:set u001 "李三,18,20010101"  
    10.            这种方式的缺点是,增加了序列化/反序列化的开销,并且在需要修改其中一项信息时,需要把整个对象取回,并且修改操作需要对并发进行保护,引入CAS等复杂问题。  
    11.        第二种方法是这个用户信息对象有多少成员就存成多少个key-value对儿,用用户ID+对应属性的名称作为唯一标识来取得对应属性的值,  
    12.            如:mset user:001:name "李三 "user:001:age18 user:001:birthday "20010101"  
    13.            虽然省去了序列化开销和并发问题,但是用户ID为重复存储,如果存在大量这样的数据,内存浪费还是非常可观的。  
    14.     那么Redis提供的Hash很好的解决了这个问题,Redis的Hash实际是内部存储的Value为一个HashMap,  
    15.     并提供了直接存取这个Map成员的接口,  
    16.         如:hmset user:001 name "李三" age 18 birthday "20010101"     
    17.             也就是说,Key仍然是用户ID,value是一个Map,这个Map的key是成员的属性名,value是属性值,  
    18.             这样对数据的修改和存取都可以直接通过其内部Map的Key(Redis里称内部Map的key为field), 也就是通过   
    19.             key(用户ID) + field(属性标签) 操作对应属性数据了,既不需要重复存储数据,也不会带来序列化和并发修改控制的问题。很好的解决了问题。  
    20.   
    21.           这里同时需要注意,Redis提供了接口(hgetall)可以直接取到全部的属性数据,但是如果内部Map的成员很多,那么涉及到遍历整个内部Map的操作,由于Redis单线程模型的缘故,这个遍历操作可能会比较耗时,而另其它客户端的请求完全不响应,这点需要格外注意。  
    22.   实现方式:  
    23.     上面已经说到Redis Hash对应Value内部实际就是一个HashMap,实际这里会有2种不同实现,这个Hash的成员比较少时Redis为了节省内存会采用类似一维数组的方式来紧凑存储,而不会采用真正的HashMap结构,对应的value redisObject的encoding为zipmap,当成员数量增大时会自动转成真正的HashMap,此时encoding为ht。


    list
    1. 常用命令:  
    2.     lpush,rpush,lpop,rpop,lrange,BLPOP(阻塞版)等。  
    3.   
    4. 应用场景:  
    5.     Redis list的应用场景非常多,也是Redis最重要的数据结构之一。  
    6.     我们可以轻松地实现最新消息排行等功能。  
    7.     Lists的另一个应用就是消息队列,可以利用Lists的PUSH操作,将任务存在Lists中,然后工作线程再用POP操作将任务取出进行执行。  
    8.   
    9. 实现方式:  
    10.     Redis list的实现为一个双向链表,即可以支持反向查找和遍历,更方便操作,不过带来了部分额外的内存开销,Redis内部的很多实现,包括发送缓冲队列等也都是用的这个数据结构。  
    11.   
    12. RPOPLPUSH source destination  
    13.   
    14.     命令 RPOPLPUSH 在一个原子时间内,执行以下两个动作:  
    15.     将列表 source 中的最后一个元素(尾元素)弹出,并返回给客户端。  
    16.     将 source 弹出的元素插入到列表 destination ,作为 destination 列表的的头元素。  
    17.     如果 source 和 destination 相同,则列表中的表尾元素被移动到表头,并返回该元素,可以把这种特殊情况视作列表的旋转(rotation)操作。  
    18.     一个典型的例子就是服务器的监控程序:它们需要在尽可能短的时间内,并行地检查一组网站,确保它们的可访问性。  
    19.     redis.lpush "downstream_ips", "192.168.0.10"  
    20.     redis.lpush "downstream_ips", "192.168.0.11"  
    21.     redis.lpush "downstream_ips", "192.168.0.12"  
    22.     redis.lpush "downstream_ips", "192.168.0.13"  
    23.     Then:  
    24.     next_ip = redis.rpoplpush "downstream_ips", "downstream_ips"  
    25.   
    26. BLPOP  
    27.   
    28.   假设现在有 job 、 command 和 request 三个列表,其中 job 不存在, command 和 request 都持有非空列表。考虑以下命令:  
    29.   BLPOP job command request 30  #阻塞30秒,0的话就是无限期阻塞,job列表为空,被跳过,紧接着command 列表的第一个元素被弹出。  
    30.   1) "command"                             # 弹出元素所属的列表  
    31.   2) "update system..."                    # 弹出元素所属的值   
    32.   为什么要阻塞版本的pop呢,主要是为了避免轮询。举个简单的例子如果我们用list来实现一个工作队列。执行任务的thread可以调用阻塞版本的pop去获取任务这样就可以避免轮询去检查是否有任务存在。当任务来时候工作线程可以立即返回,也可以避免轮询带来的延迟。  

    set 


    1. 常用命令:  
    2.     sadd,srem,spop,sdiff ,smembers,sunion 等。  
    3.   
    4. 应用场景:  
    5.     Redis set对外提供的功能与list类似是一个列表的功能,特殊之处在于set是可以自动排重的,当你需要存储一个列表数据,又不希望出现重复数据时,set是一个很好的选择,并且set提供了判断某个成员是否在一个set集合内的重要接口,这个也是list所不能提供的。  
    6.     比如在微博应用中,每个人的好友存在一个集合(set)中,这样求两个人的共同好友的操作,可能就只需要用求交集命令即可。  
    7.     Redis还为集合提供了求交集、并集、差集等操作,可以非常方便的实  
    8.   
    9. 实现方式:  
    10.     set 的内部实现是一个 value永远为null的HashMap,实际就是通过计算hash的方式来快速排重的,这也是set能提供判断一个成员是否在集合内的原因。  

    sortedset


    1. 使用场景:  
    2.     以某个条件为权重,比如按顶的次数排序.  
    3.     ZREVRANGE命令可以用来按照得分来获取前100名的用户,ZRANK可以用来获取用户排名,非常直接而且操作容易。  
    4.     Redis sorted set的使用场景与set类似,区别是set不是自动有序的,而sorted set可以通过用户额外提供一个优先级(score)的参数来为成员排序,并且是插入有序的,即自动排序。  
    5.     比如:twitter 的public timeline可以以发表时间作为score来存储,这样获取时就是自动按时间排好序的。  
    6.     比如:全班同学成绩的SortedSets,value可以是同学的学号,而score就可以是其考试得分,这样数据插入集合的,就已经进行了天然的排序。  
    7.     另外还可以用Sorted Sets来做带权重的队列,比如普通消息的score为1,重要消息的score为2,然后工作线程可以选择按score的倒序来获取工作任务。让重要的任务优先执行。  
    8.   
    9.     需要精准设定过期时间的应用  
    10.     比如你可以把上面说到的sorted set的score值设置成过期时间的时间戳,那么就可以简单地通过过期时间排序,定时清除过期数据了,不仅是清除Redis中的过期数据,你完全可以把Redis里这个过期时间当成是对数据库中数据的索引,用Redis来找出哪些数据需要过期删除,然后再精准地从数据库中删除相应的记录。  
    11.   
    12.   
    13.   实现方式:  
    14.     Redis sorted set的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序,HashMap里放的是成员到score的映射,而跳跃表里存放的是所有的成员,排序依据是HashMap里存的score,使用跳跃表的结构可以获得比较高的查找效率,并且在实现上比较简单。  


    发布订阅:

    1. Pub/Sub 从字面上理解就是发布(Publish)与订阅(Subscribe),在Redis中,你可以设定对某一个key值进行消息发布及消息订阅,  
    2.     当一个key值上进行了消息发布后,所有订阅它的客户端都会收到相应的消息。这一功能最明显的用法就是用作实时消息系统,比如普通的即时聊天,群聊等功能。  
    3.   
    4. 客户端1:subscribe  rain  
    5. 客户端2:PUBLISH  rain "my love!!!"  
    6.     (integer) 2 代表有几个客户端订阅了这个消息  

    事物:



    1.     谁说NoSQL都不支持事务,虽然Redis的Transactions提供的并不是严格的ACID的事务(比如一串用EXEC提交执行的命令,在执行中服务器宕机,那么会有一部分命令执行了,剩下的没执行),但是这个Transactions还是提供了基本的命令打包执行的功能(在服务器不出问题的情况下,可以保证一连串的命令是顺序在一起执行的,中间有会有其它客户端命令插进来执行)。  
    2.     Redis还提供了一个Watch功能,你可以对一个key进行Watch,然后再执行Transactions,在这过程中,如果这个Watched的值进行了修改,那么这个Transactions会发现并拒绝执行。  
    3. Session 1  
    4.     (1)第1步  
    5.     redis 127.0.0.1:6379> get age  
    6.     "10"  
    7.     redis 127.0.0.1:6379> watch age  
    8.     OK  
    9.     redis 127.0.0.1:6379> multi  
    10.     OK  
    11.     redis 127.0.0.1:6379>  
    12.    
    13. Session 2  
    14.     (2)第2步  
    15.     redis 127.0.0.1:6379> set age 30  
    16.     OK  
    17.     redis 127.0.0.1:6379> get age  
    18.     "30"  
    19.     redis 127.0.0.1:6379>  
    20.   
    21. Session 1     
    22.     (3)第3步  
    23.     redis 127.0.0.1:6379> set age 20  
    24.     QUEUED  
    25.     redis 127.0.0.1:6379> exec  
    26.     (nil)  
    27.     redis 127.0.0.1:6379> get age  
    28.     "30"  
    29.     redis 127.0.0.1:6379>  
    30.   
    31.     第一步,Session 1 还没有来得及对age的值进行修改  
    32.   第二步,Session 2 已经将age的值设为30  
    33.   第三步,Session 1 希望将age的值设为20,但结果一执行返回是nil,说明执行失败,之后我们再取一下age的值是30,这是由于Session   1中对age加了乐观锁导致的。  


    1.     谁说NoSQL都不支持事务,虽然Redis的Transactions提供的并不是严格的ACID的事务(比如一串用EXEC提交执行的命令,在执行中服务器宕机,那么会有一部分命令执行了,剩下的没执行),但是这个Transactions还是提供了基本的命令打包执行的功能(在服务器不出问题的情况下,可以保证一连串的命令是顺序在一起执行的,中间有会有其它客户端命令插进来执行)。  
    2.     Redis还提供了一个Watch功能,你可以对一个key进行Watch,然后再执行Transactions,在这过程中,如果这个Watched的值进行了修改,那么这个Transactions会发现并拒绝执行。  
    3. Session 1  
    4.     (1)第1步  
    5.     redis 127.0.0.1:6379> get age  
    6.     "10"  
    7.     redis 127.0.0.1:6379> watch age  
    8.     OK  
    9.     redis 127.0.0.1:6379> multi  
    10.     OK  
    11.     redis 127.0.0.1:6379>  
    12.    
    13. Session 2  
    14.     (2)第2步  
    15.     redis 127.0.0.1:6379> set age 30  
    16.     OK  
    17.     redis 127.0.0.1:6379> get age  
    18.     "30"  
    19.     redis 127.0.0.1:6379>  
    20.   
    21. Session 1     
    22.     (3)第3步  
    23.     redis 127.0.0.1:6379> set age 20  
    24.     QUEUED  
    25.     redis 127.0.0.1:6379> exec  
    26.     (nil)  
    27.     redis 127.0.0.1:6379> get age  
    28.     "30"  
    29.     redis 127.0.0.1:6379>  
    30.   
    31.     第一步,Session 1 还没有来得及对age的值进行修改  
    32.   第二步,Session 2 已经将age的值设为30  
    33.   第三步,Session 1 希望将age的值设为20,但结果一执行返回是nil,说明执行失败,之后我们再取一下age的值是30,这是由于Session   1中对age加了乐观锁导致的。  
    展开全文
  • Bloom Filter 数据结构的应用

    千次阅读 2011-02-21 15:56:00
    <br />应用1:存储字典。大家可能对于 Word 拼写...UNIX spell-checkers 将所有字典单词存成 Bloom Filter 数据结构,而后直接在 Bloom Filter 上进行查询。 出错情况:漏掉出错单词。  应用2

    应用1:存储字典。大家可能对于 Word 的拼写检查功能非常了解,当你拼错一个单词的时候,Word 会自动将这个单词用红线标注出来。 Word 的具体工作原理不得而知,但是在另一个拼写检查器 UNIX spell-checkers 这个软件中用到了 Bloom Filter。UNIX spell-checkers 将所有的字典单词存成 Bloom Filter 数据结构,而后直接在 Bloom Filter 上进行查询。

    出错的情况:漏掉出错的单词。

       应用2:数据库的 semi-join 操作。举个例子,TA 存储了 employee / city 字段, TB 存储了 city / cost of living 字段。现在需要将所有 cost of living > 50,000$ 的 employee 找出来,显然需要 join TA 和 TB。直观地看,需要将 TB 的所有 city / cost of living 字段值发给 TB,然后找到 city 相匹配的 join 一下,得出所有 employee / city 字段值。这样做是又费时又费力的。Bloom Filter 的做法是把 TB 的 city 字段做成 Bloom Filter 数据结构发给 TA,让 TA 中的 city 在这个 Bloom Filter 上做匹配,把所有找到的 employee / city 再重新发个 TB 做 join。 这样做相当于过滤掉了一部分不存在于 TA 中的city,提高了执行效率。

    出错的情况:不存在。

         应用3:分布式缓存技术。Web 缓存技术的原理是一个 proxy 如果要请求网页,它会先查看其他 proxy 是不是有这个网页,而不是直接向Web 请求。这样做可以提高下载网页的速度。为了减少网络传输的数据量,proxy 定时广播自己以 Bloom Filter 格式存储的 url,而不是把自己庞大的 url 列表广播给其他 proxy。

    出错的情况:某 proxy 以为一个 proxy 中存在某个 url,而实际上那个 proxy 中并没有这个 url。因此会造成一定的延迟。

    因为,缓存的内容频繁变化,所以 proxy 通常使用 counting bloom filter 存自己缓存的 url, 而只用 0-1 bloom filter 存别的 proxy 缓存的 url。

         应用4:p2p。p2p 技术的基本原理是 peer 从源站下载文件的同时也从其他 peer 处下载文件。通常是一个很大的文件分布式存储在很多个 peer 上,这样就要求在下载时 peer 们相互合作,peer A 需要把自己有但 peer B 没有的数据发送给 peer B,使用 bloom filter 可以方便地进行集合运算 SA-SB 来找到需要传输的数据。

    出错的情况:可能有 SA-SB 中的数据被漏掉,没有传到 peer B。

    展开全文
  • 一、java对象比较 等号(==): 对比对象实例内存地址(也即对象实例ID),来判断是否是同一对象实例;又可以说是判断对象实例是否物理相等;   equals(): 对比两个对象实例是否相等。 当对象所属类...

    一、java对象的比较

    等号(==):

    对比对象实例的内存地址(也即对象实例的ID),来判断是否是同一对象实例;又可以说是判断对象实例是否物理相等;

     

    equals():

    对比两个对象实例是否相等。

    当对象所属的类没有重写根类Object的equals()方法时,equals()判断的是对象实例的ID(内存地址),是否是同一对象实例;该方法就是使用的等号(==)的判断结果,如Object类的源代码所示:

    Java代码  收藏代码
    1. public boolean equals(Object obj) {  
    2.       return (this == obj);  
    3. }  

     
    当对象所属的类重写equals()方法(可能因为需要自己特有的“逻辑相等”概念)时,equals()判断的根据就因具体实现而异,有些类是需要比较对象的某些指或内容,如String类重写equals()来判断字符串的值是否相等。判断逻辑相等。


    hashCode():

    计算出对象实例的哈希码,并返回哈希码,又称为散列函数。根类Object的hashCode()方法的计算依赖于对象实例的D(内存地址),故每个Object对象的hashCode都是唯一的;当然,当对象所对应的类重写了hashCode()方法时,结果就截然不同了。

     


    二、Java的类为什么需要hashCode?---hashCode的作用,从Java中的集合的角度看。

      总的来说,Java中的集合(Collection)有两类,一类是List,再有一类是Set。你知道它们的区别吗?前者集合内的元素是有序的,元素可以重复;后者元素无序,但元素不可重复。那么这里就有一个比较严重的问题了:要想保证元素不重复,可两个元素是否重复应该依据什么来判断呢?这就是 Object.equals方法了。但是,如果每增加一个元素就检查一次,那么当元素很多时,后添加到集合中的元素比较的次数就非常多了。也就是说,如果集合中现在已经有1000个元素,那么第1001个元素加入集合时,它就要调用1000次equals方法。这显然会大大降低效率。

       

        于是,Java采用了哈希表的原理。哈希算法也称为散列算法,是将数据依特定算法直接指定到一个地址上。关于哈希算法,这里就不详细介绍。可以这样简单理解,hashCode方法实际上返回的就是对象存储位置的映像。
       

         这样一来,当集合要添加新的元素时,先调用这个元素的hashCode方法,就能定位到它应该放置的存储位置。如果这个位置上没有元素,它就可以直接存储在这个位置上,不用再进行任何比较了;如果这个位置上已经有元素了,就调用它的equals方法与新元素进行比较,相同的话就不存了,不相同就表示发生冲突了,散列表对于冲突有具体的解决办法,但最终还会将新元素保存在适当的位置。这样一来,实际调用equals方法的次数就大大降低了,几乎只需要一两次。
       

    所以,Java对于eqauls方法和hashCode方法是这样规定的:
    1、相等的对象必须具有相等的哈希码(或者散列码)。
    2、如果两个对象的hashCode相同,它们并不一定相同。
      
     上述的对象相同指的是通过eqauls方法判断,结果为true。

     你当然可以不按要求去做了,但你会发现,相同的对象可以出现在Set集合中。同时,增加新元素的效率会大大下降。


     

    三、深入解析HashMap类的底层数据结构

    Map接口
      Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个 value。Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射。

     

    Hashtable类
      Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。添加数据使用put(key, value),取出数据使用get(key),这两个基本操作的时间开销为常数。
       

        Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大,这会影响像get和put这样的操作。
    使用Hashtable的简单示例如下,将1,2,3放到Hashtable中,他们的key分别是”one”,”two”,”three”:
        Hashtable numbers = new Hashtable();
        numbers.put(“one”, new Integer(1));
        numbers.put(“two”, new Integer(2));
        numbers.put(“three”, new Integer(3));
      要取出一个数,比如2,用相应的key:
        Integer n = (Integer)numbers.get(“two”);
        System.out.println(“two = ” + n);

     
    1.    HashMap概述:
       HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
     
    2.    HashMap的数据结构:
        HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。首先,HashMap类的属性中定义了Entry类型的数组。Entry类实现java.ultil.Map.Entry接口,同时每一对key和value是作为Entry类的属性被包装在Entry的类中。
     

    如图所示,HashMap的数据结构:


     

     

     

       HashMap的部分源码如下:

    Java代码  收藏代码
    1. /** 
    2.  * The table, resized as necessary. Length MUST Always be a power of two. 
    3.  */  
    4.   
    5. transient Entry[] table;  
    6.    
    7. static class Entry<K,V> implements Map.Entry<K,V> {  
    8.     final K key;  
    9.     V value;  
    10.     Entry<K,V> next;  
    11.     final int hash;  
    12.     ……  
    13. }  

     
        可以看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。table数组的元素是Entry类型的。每个 Entry元素其实就是一个key-value对,并且它持有一个指向下一个 Entry元素的引用,这就说明table数组的每个Entry元素同时也作为某个Entry链表的首节点,指向了该链表的下一个Entry元素,这就是所谓的“链表散列”数据结构,即数组和链表的结合体。


     
    3.    HashMap的存取实现:


       1) 添加元素:

    当我们往HashMap中put元素的时候,先根据key的重新计算元素的hashCode,根据hashCode得到这个元素在table数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

    HashMap的部分源码如下:

    Java代码  收藏代码
    1. public V put(K key, V value) {  
    2.    // HashMap允许存放null键和null值。  
    3.    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。  
    4.    if (key == null)  
    5.        return putForNullKey(value);  
    6.    // 根据key的keyCode重新计算hash值。  
    7.    int hash = hash(key.hashCode());  
    8.    // 搜索指定hash值在对应table中的索引。  
    9.    int i = indexFor(hash, table.length);  
    10.    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。  
    11.    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
    12.        Object k;  
    13.       // 如果发现 i 索引处的链表的某个Entry的hash和新Entry的hash相等且两者的key相同,则新Entry覆盖旧Entry,返回。  
    14.        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
    15.            V oldValue = e.value;  
    16.            e.value = value;  
    17.            e.recordAccess(this);  
    18.            return oldValue;  
    19.        }  
    20.    }  
    21.    // 如果i索引处的Entry为null,表明此处还没有Entry。  
    22.    modCount++;  
    23.    // 将key、value添加到i索引处。  
    24.    addEntry(hash, key, value, i);  
    25.    return null;  

     

     2) 读取元素:

    有了上面存储时的hash算法作为基础,理解起来这段代码就很容易了。从上面的源代码中可以看出:从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。

    HashMap的部分源码如下:

    Java代码  收藏代码
    1. public V get(Object key) {  
    2.     if (key == null)  
    3.         return getForNullKey();  
    4.     int hash = hash(key.hashCode());  
    5.     for (Entry<K,V> e = table[indexFor(hash, table.length)];  
    6.         e != null;  
    7.         e = e.next) {  
    8.         Object k;  
    9.         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
    10.             return e.value;  
    11.     }  
    12.     return null;  
    13. }  

      
       
      
       3) 归纳起来简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。

       

    四、关于“相等的对象必须具有相等的哈希码”

      由于作为key的对象将通过计算其散列函数hashCode()来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object,如果你用自定义的类当作key的话,要相当小心,按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同,如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。
      如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),要避免这种问题,只需要牢记一条:要同时复写equals方法和hashCode方法,而不要只写其中一个。


    同时复写equals方法和hashCode方法,必须保证“相等的对象必须具有相等的哈希码”,也就是当两个对象通过equals()比较的结果为true时,这两个对象调用hashCode()方法生成的哈希码必须相等。

     

    如何保证相等,可以参考下面的方法:

        复写equals方法和hashCode方法时,equals方法的判断根据和计算hashCode的依据相同。如String的equals方法是比较字符串每个字符,String的hashCode也是通过对该字符串每个字符的ASC码简单的算术运算所得,这样就可以保证相同的字符串的hashCode相同且equals()为真。

     

    String类的equals方法的源代码:

    Java代码  收藏代码
    1.    /** 
    2.     * Compares this string to the specified object.  The result is {@code 
    3.     * true} if and only if the argument is not {@code null} and is a {@code 
    4.     * String} object that represents the same sequence of characters as this 
    5.     * object. 
    6.     * 
    7.     * @param  anObject 
    8.     *         The object to compare this {@code String} against 
    9.     * 
    10.     * @return  {@code true} if the given object represents a {@code String} 
    11.     *          equivalent to this string, {@code false} otherwise 
    12.     * 
    13.     * @see  #compareTo(String) 
    14.     * @see  #equalsIgnoreCase(String) 
    15.     */  
    16.    public boolean equals(Object anObject) {  
    17. if (this == anObject) {  
    18.     return true;  
    19. }  
    20. if (anObject instanceof String) {  
    21.     String anotherString = (String)anObject;  
    22.     int n = count;  
    23.     if (n == anotherString.count) {  
    24.     char v1[] = value;  
    25.     char v2[] = anotherString.value;  
    26.     int i = offset;  
    27.     int j = anotherString.offset;  
    28.     while (n-- != 0) {  
    29.         if (v1[i++] != v2[j++])  
    30.         return false;  
    31.     }  
    32.     return true;  
    33.     }  
    34. }  
    35. return false;  
    36.    }  

     

    String类的hashCode方法计算hashCode的源代码:

    Java代码  收藏代码
    1.    /** 
    2.     * Returns a hash code for this string. The hash code for a 
    3.     * <code>String</code> object is computed as 
    4.     * <blockquote><pre> 
    5.     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 
    6.     * </pre></blockquote> 
    7.     * using <code>int</code> arithmetic, where <code>s[i]</code> is the 
    8.     * <i>i</i>th character of the string, <code>n</code> is the length of 
    9.     * the string, and <code>^</code> indicates exponentiation. 
    10.     * (The hash value of the empty string is zero.) 
    11.     * 
    12.     * @return  a hash code value for this object. 
    13.     */  
    14.    public int hashCode() {  
    15. int h = hash;  
    16.        int len = count;  
    17. if (h == 0 && len > 0) {  
    18.     int off = offset;  
    19.     char val[] = value;  
    20.   
    21.            for (int i = 0; i < len; i++) {  
    22.                h = 31*h + val[off++];  
    23.            }  
    24.            hash = h;  
    25.        }  
    26.        return h;  
    27.    }  

     来自:http://kakajw.iteye.com/blog/935226


    展开全文
  • 假设表达式中允许包含两种括号:圆括号和方括号,其嵌套顺序随意,及([]())或[([][])]等均为正确格式,[(])或([())或(()]均为不正确格式。 匹配算法思想是: 首先将第一个括号压入栈,然后从...
  • 算法基于原理:  N = (N / d)×d + N % d 其中: N——十进制数 d——目标数制基数   以十进制数1348转换到八进制数举例,其运算过程如下: <br />(来源:数据结构 严蔚敏...
  • 数据结构应用——链表的应用

    千次阅读 2019-06-28 20:48:32
    利用链表数据结构设计程序完成n阶乘运算及输出 累计运算中间结果和最终计算结果数据类型要求是整型 需设计合适存储结构,要求每个元素或结点最多存储数据3位数值 基于设计存储结构实现乘法操作,...
  • 数据结构核心原理与算法应用

    千人学习 2019-09-03 17:50:03
    为此,樊老师结合多年工作经验,经过长时间准备,精心打造了《数据结构基本原理与算法应用》课程,本课程不拘泥于任何一门编程语言,从实际应用出发,深入浅出,注重学员对于课程知识整体掌握与深入理解。...
  • 数据结构的应用

    千次阅读 2018-06-25 15:09:05
    设计城市之间交通路线图,有6个城市(上海、北京、南京、扬州、南通、苏州),已知城市间拟建设公路。两城市间建设经济费用自己输入。要建设一个连接6个城市交通网,使得任意两个城市之间都可以直接或间接到达...
  • 数据结构——图的应用

    千次阅读 2019-07-23 20:38:50
    在图型数据结构中,数据被称为顶点,数据之间关系补称为边。 在图中不允许出现没有点,但可以没有边。 G(V,E),V表示顶点集合,E表示边集合。 各种图定义: 无向图:顶点与顶点之间没有方向,这种边称为无向...
  • 数据结构与算法的应用场景

    千次阅读 2017-11-28 20:41:02
    1. 概述 数据结构与算法可以按以下类别分类: 通用数据结构:数组、链表、树、...2. 通用数据结构应用场景 数组和链表是最慢,树相对较快,哈希表是最快。 但是并非使用最快结构是最好方案,因为最快
  • 数据结构~09.顺序栈和链栈的应用

    万次阅读 热门讨论 2020-07-29 19:11:43
    数据结构学习~09.顺序栈和链栈的应用 本文是上一篇文章的后续,详情点击该链接~
  • 各种数据结构及其应用场景

    千次阅读 2019-10-11 17:31:10
    1. 常用数据结构及其应用场景: https://www.jianshu.com/p/ec17d738327f 2. 代码可执行文件内存占用:【https://blog.csdn.net/u012942555/article/details/48876447】 首先要来理解一下可执行文件加载进内存...
  • 二叉树的应用详解 - 数据结构

    万次阅读 多人点赞 2012-06-25 11:45:05
    概述: 平衡树——特点:所有结点左右子树深度差≤1 排序树——特点:所有结点“左小右...最优树——是带权路径长度最短树,又称 Huffman树,用途之一是通信中压缩编码。 1. 二叉排序树(二叉查找树Binary Sear
  • 该视频教程教大家将学到的数据结构与算法知识应用到实际项目开发中,真正做到学以致用,理论联系实际,课程会从基本的数据结构算法讲起,结合着实际项目开发,由浅入深,更加贴近实战,让学习者真正掌握算法应用...
  • 数据结构在游戏中简单应用

    千次阅读 2016-06-08 06:43:37
    在游戏的编写中,不可避免的出现很多应用数据结构的地方,有些简单的游戏,只是由几个数据结构的组合,所以说,数据结构在游戏编程中扮演着很重要的角色。  本文主要讲述数据结构在游戏中的应用,其中包括对链表、顺序表...
  • 常见数据结构应用场景

    千次阅读 2018-10-06 19:52:58
    删除操作和和修改操作都是建立在查找操作上,所以完美的数据结构应该是具有较高插入效率和查找效率。 通用数据结构关系 可以根据下图选择合适通用数据结构: 数组 使用场景 数组在以下三个情形下很...
  • 数据结构~13.遍历二叉树四个应用案例

    万次阅读 多人点赞 2020-08-08 11:45:52
    数据结构学习~13.二叉树深度 本文是上一篇文章后续,详情点击该链接~
  • 十、Python语言中简单数据结构的应用(之一) ----From a high school student's view to learn Python 关键字: python 列表 堆栈 数据结构 递归调用 函数 组合问题 后缀表达式 前缀表达式 逆波兰表达式 运算符 ...
  • 常用数据结构应用场景

    千次阅读 2018-03-19 16:56:41
    通用数据结构可以简单按照速度将通用数据结构划分为:数组和链表(最慢),树(较快),哈希表(最快)。增、删、改、查是四大常见操作,不过其实可以浓缩为两个操作:增和查。删除操作和和修改操作都是建立在查找...
  • 数据结构——串基本操作与应用

    千次阅读 2018-11-18 21:24:51
    数据结构中栈和队列是比较重要的,今天贴下串的一些应用。 ...4、 熟练掌握串的应用。 二、实验内容 用串的堆结构,实现串的基本操作,程序界面如下 #include&lt;stdio.h&gt; #include...
  • 典型数据结构的常见应用

    千次阅读 2006-08-20 19:44:00
    很多复杂的数据结构都是基于数组和链表来进行实现的,所以学好二者对于数据结构的学习很重要。数组数组适合于那些需要对元素进行快速查找,插入和删除动作不多的应用。需要注意的是:如果使用静态数组的话,就有容量...
  • redis5种数据结构应用场景介绍

    千次阅读 2018-07-05 12:14:07
    在服务端为了减轻高并发下数据库访问压力,经常要应用缓存。redis和memcached都可以作为缓存系统使用,redis与memcached一样,为了保证效率,数据都是缓存在内存中,读写性能差距不大。区别是redis会周期性把...
  • 【说明】本文来自由周世平老师主编的《C语言程序设计》教材。我作为参编人员执笔了第7、8章。“第8章 问题求解与算法”中“8.6.1 回溯法”以8皇后问题的求解为例,介绍了回溯...对于数据结构的学习者而言,由于知识面的
  • 数据结构之串的应用

    千次阅读 2017-06-27 12:10:01
    串即字符串,是最基本非数值数据之一,它是一种特殊线性表,特殊在于组成线性表每一个元素都是一个字符。串顺序存储定义:typedef struct { char ch[max]; int len; }seqstring;串链式存储定义:typedef...
  • 数据结构例程——两个表的自然连接本文针对数据结构基础系列网络课程(2):线性表中第14课时线性表的应用。问题:有表A,m1行、n1列,表B,m2行、n2列,求A和B的自然连接结果C 例: 解答:#include #include #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 102,950
精华内容 41,180
关键字:

数据结构的应用

数据结构 订阅