Hash(散列)

  • 数组与链表数据结构存储数据的方式:
因为数组删除、插入操作时,同时需要操作后面的元素,所以增、删效率较低,而链表的结构导致了查找的效率较低,我们是否可以构造一个关系,使得待存储的集合{a,b,c,d,e,f}中的任意一个元素通过这个关系都能找到一个指定的索引值,所以现在假设有一种方法f,可以将各个元素和存储位置对应起来,那么这个方法f就是hash函数(散列函数)。

根据上图我们知道原有集合中的元素被散列之后所得到的有序对的集合为{(d,0),(b,2),(c,2),(a,3),(f,4),(e,5)}。其中,散列表中的1号槽为空,表示经过散列函数作用之后,原集合中没有任何元素被散列至该位置,而2号槽中则存在两个元素,将两个不同元素散列至相同位置的情形我们称为碰撞(Collision)。【hashMap中碰撞发生时,用链表进行存储,存储结构中包含key和value,当进行查找时,先查找hashCode找到对应槽(桶?bucket?),然后在链表中根据key进行查找value】

 

  • 常用的散列函数:
    1、除余法
    顾名思义,除余法就是用关键码x除以M(往往取散列表长度),并取余数作为散列地址。除余法几乎是最简单的散列方法,散列函数为: h(x) = x mod M。

 

 

  • 冲突解决的策略

尽管散列函数的目标是使得冲突最少,但实际上冲突是无法避免的。因此,我们必须研究冲突解决策略。冲突解决技术可以分为两类:开散列方法( open hashing,也称为拉链法,separate chaining )和闭散列方法( closed hashing,也称为开地址方法,open addressing )。这两种方法的不同之处在于:开散列法把发生冲突的关键码存储在散列表主表之外,而闭散列法把发生冲突的关键码存储在表中另一个槽内。

开散列方法:

1、拉链法

开散列方法的一种简单形式是把散列表中的每个槽定义为一个链表的表头。散列到一个特定槽的所有记录都放到这个槽的链表中。图9-5说明了一个开散列的散列表,这个表中每一个槽存储一个记录和一个指向链表其余部分的指针。这7个数存储在有11个槽的散列表中,使用的散列函数是h(K) = K mod 11。数的插入顺序是77、7、110、95、14、75和62。有2个值散列到第0个槽,1个值散列到第3个槽,3个值散列到第7个槽,1个值散列到第9个槽。

 

哈希表有多种不同的实现方法,最常用的一种方法就是 拉链法,可以理解为“链表的数组” ,如图:

从上图我们可以发现哈希表是由数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。

首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

 

2、桶式散列

桶式散列方法的基本思想是把一个文件的记录分为若干存储桶,每个存储桶包含一个或多个页块,一个存储桶内的各页块用指针连接起来,每个页块包含若干记录。散列函数h把关键码值K转换为存储桶号,即h(K)表示具有关键码值K的记录所在的存储桶号。 图9-6表示了一个具有B个存储桶的散列文件组织。有一个存储桶目录表,存放B个指针,每个存储桶一个,每个指针就是所对应存储桶的第一个页块的地址。

有些存储桶仅仅由一个页块组成,如下图中的1号存储桶。有的存储桶由多个页块组成,每一个页块的块头上有一个指向下一个页块的指针,例如,如下图中的第B-1号存储桶由b4,b5,b6三个页块组成,每个存储桶中最后一个页块的头上为空指针。

 

摘录自:http://blog.csdn.net/koself/article/details/7869453

http://blog.csdn.net/jn1158359135/article/details/7205688

http://blog.csdn.net/vking_wang/article/details/14166593

发表评论

邮箱地址不会被公开。 必填项已用*标注