如何解决Hash中的冲突问题

1、开放定址法

用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。注意：

①用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。

②空单元的表示与具体的应用相关。

按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。

（1）线性探查法(Linear Probing)

该方法的基本思想是：

将散列表T[0m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：

d，d+l，d+2，…，m-1，0，1，…，d-1

即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到 T[d-1]为止。

探查过程终止于三种情况：

(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；

(2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；

(3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。

利用开放地址法的一般形式，线性探查法的探查序列为：

hi=(h(key)+i)％m 0≤i≤m-1 //即di=i

用线性探测法处理冲突，思路清晰，算法简单，但存在下列缺点：

① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找。

② 按上述算法建立起来的哈希表，删除工作非常困难。假如要从哈希表 HT 中删除一个记录，按理应将这个记录所在位置置为空，但我们不能这样做，而只能标上已被删除的标记，否则，将会影响以后的查找。

③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。

（2）线性补偿探测法

线性补偿探测法的基本思想是：

将线性探测的步长从 1 改为 Q ，即将上述算法中的 j ＝ (j ＋ 1) % m 改为： j ＝ (j ＋ Q) % m ，而且要求 Q 与 m 是互质的，以便能探测到哈希表中的所有单元。

例 PDP-11 小型计算机中的汇编程序所用的符合表，就采用此方法来解决冲突，所用表长 m ＝ 1321 ，选用 Q ＝ 25 。 2、拉链法

（1）拉链法解决冲突的方法

拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数 组T[0m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。

例设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所建立的哈希表如下图所示：

（2）拉链法的优点

与开放定址法相比，拉链法有如下几个优点：

①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；

②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；

③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；

④在用拉链法构造的散列表中，删除结点的 *** 作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除 *** 作，只能在被删结点上做删除标记，而不能真正删除结点。

（3）拉链法的缺点

拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

太多了

比方说用图的方法，每一个哈希值设一个链条，如果有冲突，就加入到对应哈希的那个链条

比方说用顺序存储的方法，预先留下一定数量的空的内存单元来摆放将来发生冲突的值

这些在很多数据结构的书里面都有写。。。希望你去找一下。。。太多。。。。

哈希计算就是努力的把比较大的数据存放到相对较小的空间中。

最常见的哈希算法是取模法。

下面简单讲讲取模法的计算过程。

比如：数组的长度是5。这时有一个数据是6。那么如何把这个

6存放到长度只有5的数组中呢。按照取模法，计算

6％5，结果是1，那么就把6放到数组下标是1的位置。那么，7

就应该放到2这个位置。到此位置，哈斯冲突还没有出现。

这时，有个数据是11，按照取模法，11％5＝1，也等于1。那么

原来数组下标是1的地方已经有数了，是6。这时又计算出1这个

位置，那么数组1这个位置，就必须储存两个数了。这时，就叫

哈希冲突。冲突之后就要按照顺序来存放了。

如果数据的分布比较广泛，而且储存数据的数组长度比较大。

那么哈希冲突就比较少。否则冲突是很高的。

具体的算法你要参照更加专业的书籍。

希望对你有帮助。

java hashmap 得到指定key的value的方法：

private static ArrayList valueGetKey(Map map,String value) 

{

    Set set = mapentrySet();//新建一个不可重复的集合

    

    ArrayList arr = new ArrayList<>();//新建一个集合

    

    Iterator it = setiterator();//遍历的类

    while(ithasNext()) 

    {

      MapEntry entry = (MapEntry)itnext();//找到所有key-value对集合

      

      if(entrygetValue()equals(value)) //通过判断是否有该value值

      {

        

        int s = (int)entrygetKey();//取得key值

        

        arradd(s);

        

      }

    }

    return arr;

在hash碰撞的情况下，主要的处理方法有：

1开放地址法

开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)

基本思想：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。

2rehash（再hash法）

使用第二个或第三个计算地址，知道无冲突。比如：按首字母进行hash冲突了，则按照首字母第二位，进行hash寻址。

3链地址法（拉链法）

创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

java hashmap使用的就是拉链法解决hash碰撞。

哈希表是由链表+数组组成。

通过hash(key)%len存储到相对应的数组中，如140%16=12意味着数组下标相同，并不表示hashCode相同。

Redis不仅仅是一个简单的key-value内存数据库，Redis官网对自身的定义是“数据结构服务器”。通过用心设计各种数据结构类型的数据存储，可以实现部分的数据查询功能。因为在Redis的设计中，key是一切，对于Redis是可见的，而value对于Redis来说就是一个字节数组，Redis并不知道你的value中存储的是什么，所以要想实现比如

‘select from users where userlocation="shanghai"’

这样的查询，在Redis是没办法通过value进行比较得出结果的。但是可以通过不同的数据结构类型来做到这一点。比如如下的数据定义

users:1 {name:Jack,age:28,location:shanghai}

users:2 {name:Frank,age:30,location:beijing}

users:location:shanghai [1]

其中users:1 users:2 分别定义了两个用户信息，通过Redis中的hash数据结构，而users:location:shanghai 记录了所有上海的用户id，通过集合数据结构实现。这样通过两次简单的Redis命令调用就可以实现我们上面的查询。

Jedis jedis = jedisPoolgetResource();

Set<String> shanghaiIDs = jedissmembers("users:location:shanghai");

//遍历该set

//

//通过hgetall获取对应的user信息

jedishgetAll("users:" + shanghaiIDs[0]);

通过诸如以上的设计，可以实现简单的条件查询。但是这样的问题也很多，首先需要多维护一个ID索引的集合，其次对于一些复杂查询无能为力(当然也不能期望Redis实现像关系数据库那样的查询，Redis不是干这的)。

但是Redis26集成了Lua脚本，可以通过eval命令，直接在RedisServer环境中执行Lua脚本，并且可以在Lua脚本中调用Redis命令。其实，就是说可以让你用Lua这种脚本语言，对Redis中存储的key value进行 *** 作，这个意义就大了，甚至可以将你们系统所需的各种业务写成一个个lua脚本，提前加载进入Redis，然后对于请求的响应，只需要调用一个个lua脚本就行。当然这样说有点夸张，但是意思就是这样的。

比如，现在我们要实现一个‘所有age大于28岁的user’这样一个查询，那么通过以下的Lua脚本就可以实现

public static final String SCRIPT =

"local resultKeys={};"

+ "for k,v in ipairs(KEYS) do "

+ " local tmp = rediscall('hget', v, 'age');"

+ " if tmp > ARGV[1] then "

+ " tableinsert(resultKeys,v);"

+ " end;"

+ "end;"

+ "return resultKeys;";

执行脚本代码

Jedis jedis = jedisPoolgetResource();

jedisauth(auth);

List<String> keys = ArraysasList(allUserKeys);

List<String> args = new ArrayList<>();

argsadd("28");

List<String> resultKeys = (List<String>)jedisevalsha(funcKey, keys, args);

return resultKeys;

注意，以上的代码中使用的是evalsha命令，该命令参数的不是直接Lua脚本字符串，而是提前已经加载到Redis中的函数的一个SHA索引，通过以下的代码将系统中所有需要执行的函数提前加载到Redis中，我们的系统维护一个函数哈希表，后续需要实现什么功能，就从函数表中获取对应功能的SHA索引，通过evalsha调用就行。

String shaFuncKey = jedisscriptLoad(SCRIPT);//加载脚本，获取sha索引

funcTableput(funcName_age, shaFuncKey);//添加到函数表中

通过以上的方法，便可以使较为复杂的查询放到Redis中去执行，提高效率。

哈希表（散列表 Hash）是相对于线性表、树形结构的一种数据结构，它能在元素的存储位置和其关键字直接建立某种之间关系，那么在进行查找时，就无需做或者做很少次的比较，就能通过这个关系直接由关键字找到对对应的记录。这就是散列查找法（Hase Search）的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址。即使用关键字到地址的直接转换方法，而不需要反复比较。因此，散列查找法又叫杂凑法或者散列法。

选择一个好的散列函数可以在一定程度上减少冲突，但在实际应用中，很难完全避免发生冲突，所以选择一个有效的处理冲突的方法是散列表的另一个关键问题。

处理冲突的方法与散列表本身的组织形式有关。按组织形式的不同，通常分为两大类：开放地址法和链地址法。

开放地址法的基本思想是：把记录都存储在散列表数组中，当某一记录关键字key的初始散列地址H0=H(key)发生冲突时，以H0为基础，采取合适方法计算得到另一地址H1，如果H1仍然发生冲突，已H1位基础再求下一个地址H2，若H2仍然冲突，再求得H3，以此类推，直至Hk不发生冲突为止，则Hk为该记录在表中的散列地址。

根据计算方法，可以分为以下三种探测方法：

线性探测法会在出现在处理过程中发生冲突的发生第一个散列地址不同的记录争夺同一个后继散列地址的现象，称为二次聚集或者堆积。即在处理同义词的冲突过程中，又添加了非同义词的冲突。

它的优点是，只要散列表未满，就一定能找到一个不发生冲突的地址

而二次探测法和伪随机数探测法可以避免出现二次聚集现象，但是不保证一定能找到不发生冲突的地址。

链地址法的基本思想是：把具有相同散列地址的记录放在同一个单链表中，称为同义词链表。有m个散列地址就有m个单链表，同时用数组HT[0m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点的方式插入已HT[i]为头结点的单链表中。

以上就是关于如何解决Hash中的冲突问题全部的内容，包括:如何解决Hash中的冲突问题、hash表的hash函数，冲突解决方法有哪些、什么是哈希冲突等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！