精华内容
下载资源
问答
  • 开放地址法

    千次阅读 2019-05-03 15:28:02
    哈希表在压缩可选值后仍有冲突的可能,比如1和101,二者最后的取余仍为1,会导致冲突,解决这种冲突的一种方法就是开放地址法开放地址法:当冲突法生时,通过查找数组的一个空位,并将数据填入,而不再用哈希...

    哈希表在压缩可选值后仍有冲突的可能,比如1和101,二者最后的取余仍为1,会导致冲突,解决这种冲突的一种方法就是开放地址法。

     

    开放地址法:当冲突法生时,通过查找数组的一个空位,并将数据填入,而不再用哈希函数得到的数组下表

     

    简单的理解:就是当发生冲突的时候,比如1和101,1占据了一个位置,101进入时候就向下查找,找到下面的一个空位插入, 如果没有继续查找空位,知道找到为止并进行插入。

     

    代码实现:

    初始化


    /**
     * 员工信息类
     * @author Administrator
     *
     */
    public class Info {
        private String key;
        private String name;
        
        public Info(String key, String name) {
            this.key = key;
            this.name = name;
        }

        public String getKey() {
            return key;
        }

        public void setKey(String key) {
            this.key = key;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }
        
        
    }

    定义方法

     

     

    import java.math.BigInteger;

    public class HashTable {
        private Info[] arr;
        
        /**
         * 默认的构造方法
         */
        public HashTable() {
            arr = new Info[100];
        }
        
        /**
         * 指定数组初始化大小
         */
        public HashTable(int maxSize) {
            arr = new Info[maxSize];
        }
        
        /**
         * 插入数据
         */
        public void insert(Info info) {
            //获得关键字
            String key = info.getKey();
            //关键字所自定的哈希数
            int hashVal = hashCode(key);
            //如果这个索引已经被占用,而且里面是一个未被删除的数据
            while(arr[hashVal] != null && arr[hashVal].getName() != null) {
                //进行递加
                ++hashVal;
                //循环
                hashVal %= arr.length;
            }
            arr[hashVal] = info;
        }
        
        /**
         * 查找数据
         */
        public Info find(String key) {
            int hashVal = hashCode(key);
            while(arr[hashVal] != null) {
                if(arr[hashVal].getKey().equals(key)) {
                    return arr[hashVal];
                }
                ++hashVal;
                hashVal %= arr.length;
            }
            return null;
        }
        
        /**
         * 删除数据
         * @param key
         * @return
         */
        public Info delete(String key) {
            int hashVal = hashCode(key);
            while(arr[hashVal] != null) {
                if(arr[hashVal].getKey().equals(key)) {
                    Info tmp = arr[hashVal];
                    tmp.setName(null);
                    return tmp;
                }
                ++hashVal;
                hashVal %= arr.length;
            }
            return null;
        }
        
        public int hashCode(String key) {
    //        int hashVal = 0;
    //        for(int i = key.length() - 1; i >= 0; i--) {
    //            int letter = key.charAt(i) - 96;
    //            hashVal += letter;
    //        }
    //        return hashVal;
            
            BigInteger hashVal = new BigInteger("0");
            BigInteger pow27 = new BigInteger("1");
            for(int i = key.length() - 1; i >= 0; i--) {
                int letter = key.charAt(i) - 96;
                BigInteger letterB = new BigInteger(String.valueOf(letter));
                hashVal = hashVal.add(letterB.multiply(pow27));
                pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
            }
            return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
        }
    }

     

    进行测试

     

    public class TestHashTable {
        public static void main(String[] args) {
            HashTable ht = new HashTable();
            ht.insert(new Info("a","张三"));
            ht.insert(new Info("ct","李四"));
            ht.insert(new Info("b","王五"));
            
            System.out.println(ht.find("a").getName());
            System.out.println(ht.find("ct").getName());
            System.out.println(ht.find("b").getName());
            
            ht.delete("b");
            System.out.println(ht.find("b").getName());
        }
    }

     

    展开全文
  • 主要介绍了java开放地址法和链地址法解决hash冲突的方法示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 开放地址法java代码

    2012-04-16 15:48:35
    开放地址法java代码
  • Hash冲突之开放地址法

    万次阅读 2020-07-29 07:30:09
    所谓开放地址法就是发生冲突时在散列表(也就是数组里)里去寻找合适的位置存取对应的元素。 一、线性探测法 若当前位置冲突了,就去找相邻的下一个位置。 就拿放入元素举例吧,当你放入<a,101>到下标为2的...

    Hash函数:将任意长度的输入转化成固定长度的输出的一类函数。

    所谓开放地址法就是发生冲突时在散列表(也就是数组里)里去寻找合适的位置存取对应的元素。

    一、线性探测法

    若当前位置冲突了,就去找相邻的下一个位置。

    就拿放入元素举例吧,当你放入<a,101>到下标为2的位置后,另一个<c,103>键值对也落入了这个位置,那么它就向后依次加一寻找合适的位置,然后把<c,103>放入进去。

    在这里插入图片描述

    在这里插入图片描述

    我们把这种方法称作线性探测法,我们可以将Hash以及寻找位置的过程抽象成一个函数:

    在这里插入图片描述

    所以关键字要进行查找或者插入,首先看(hash1(key)+0)%7 位置是自己最终的位置吗?如果有冲突,就探测(查看)下一个位置:(hash1(key)+1)%7。依次进行。

    但是这样会有一个问题,就是随着键值对的增多,会在哈希表里形成连续的键值对。

    在这里插入图片描述

    这样的话,当插入元素时,任意一个落入这个区间的元素都要一直探测到区间末尾,并且最终将自己加入到这个区间内。这样就会导致落在区间内的关键字Key要进行多次探测才能找到合适的位置,并且还会继续增大这个连续区间,使探测时间变得更长,这样的现象被称为“一次聚集(primary clustering)”。

    在这里插入图片描述
    在这里插入图片描述

    二、平方探测法

    我们可以在探测时不一个挨着一个地向后探测,我们可以跳跃着探测,这样就避免了一次聚集。

    其实我们可以让它按照 i^2 的规律来跳跃探测。

    在这里插入图片描述
    在这里插入图片描述

    这样的话,元素就不会聚集在某一块区域了,我们把这种方法称为平方探测法

    同样我们可以抽象成下面的函数:

    在这里插入图片描述
    其实可以扩展到更一般的形式:
    在这里插入图片描述
    虽然平方探测法解决了线性探测法的一次聚集,但是它也有一个小问题,就是关键字key散列到同一位置后探测时的路径是一样的。
    在这里插入图片描述
    这样对于许多落在同一位置的关键字而言,越是后面插入的元素,探测的时间就越长。

    这种现象被称作“二次聚集(secondary clustering)”,其实这个在线性探测法里也有。

    这种现象出现的原因是由于对于落在同一个位置的关键字我们采取了一个依赖 i 的函数(i或者i^2)来进行探测,它不会因为关键字的不同或其他因素而改变探测的路径。那么我们是不是可以让探测的方法依赖于关键字呢?

    三、双散列

    答案是可以的,我们可以再弄另外一个Hash函数,对落在同一个位置的关键字进行再次的Hash,探测的时候就用依赖这个Hash值去探测,比如我们可以使用下面的函数:
    在这里插入图片描述
    经过hash1的散列后,会定位到某一个地址,如果这个地址冲突,那么就按照1hash2(key)、2hash2(key)… 的偏移去探测合适的位置。
    在这里插入图片描述
    由于Hash2函数不同于Hash1,所以两个不同的关键字Hash1值和Hash2值同时相同的概率就会变得非常低。

    这样就避免了二次聚集,但同时也付出了计算另一个散列函数Hash2的代价。

    如果hash2(key)=0,那探测不就一直在原地不动,所以hash2函数在选择的时候要避免这种情况。

    展开全文
  • 哈希表之开放地址法

    千次阅读 2018-05-02 15:52:21
    哈希表中解决一个单元多个数据项的冲突问题,有2种办法:开放地址法和链地址法。开放地址法是在数据项具有相同下标时在数组中其他地方寻找一个空白单元放置要插入的数据项;链地址法是数组存储的是链表,相同下标的...

    哈希表中解决一个单元多个数据项的冲突问题,有2种办法:开放地址法和链地址法。开放地址法是在数据项具有相同下标时在数组中其他地方寻找一个空白单元放置要插入的数据项;链地址法是数组存储的是链表,相同下标的数据项只需要连到链表上去即可。

    哈希表的容量一般设置为素数,因为无论按照何种步长,总可以遍历素数。

    其中,开放地址法有3种方法:

    1,线性探测:线性探测是逐步搜索空的位置。缺点:数据项聚集,越来越大,越后面找到空位插入数据项需要时间越多

    import java.util.Random;

    //假设数据都是正整数
    class DataItem {
        int data;

        public DataItem(int data) {
            this.data = data;
        }
    }

    public class LHashFind {
        // 数据量最好在一半到2/3之间
        private int size;
        private DataItem[] itemArray;
        private DataItem deletedItem;

        public LHashFind(int size) {
            this.size = size;
            itemArray = new DataItem[size];
            deletedItem = new DataItem(-1);
        }

        // 以下方法只在数组不满时使用,否则可能死循环
        public DataItem find(int key) {
            int hashval = hashfunc(key);
            while (itemArray[hashval] != null) {
                if (itemArray[hashval].data == key)
                    return itemArray[hashval];
                hashval++;
                hashval %= size;
            }
            return null;
        }

        private int hashfunc(int key) {
            return key % size;
        }

        public void insert(int key) {
            DataItem item = new DataItem(key);
            int hashval = hashfunc(key);
            while (itemArray[hashval] != null && itemArray[hashval].data != -1) {
                hashval++;
                hashval %= size;
            }
            itemArray[hashval] = item;
        }

        public DataItem delete(DataItem item) {
            int hashval = hashfunc(item.data);
            while (itemArray[hashval] != null) {
                if (itemArray[hashval].data == item.data) {
                    DataItem temp = itemArray[hashval];
                    itemArray[hashval] = deletedItem;
                    return temp;
                }
                hashval++;
                hashval %= size;
            }
            return null;
        }

        public void display() {
            for (int i = 0; i < size; i++) {
                if (itemArray[i] != null)
                    System.out.print(itemArray[i].data + " ");
                else
                    System.out.print(0 + " ");
            }
            System.out.println();
        }

        // 哈希表扩容:不是简单复制,而是重新插入到新的数组
        public void reHash() {
            int newSize = reSize(size);// 得到一个大于2倍size的素数newSize
            DataItem[] newArray = new DataItem[newSize];
            int key, hashval;
            for (int i = 0; i < size; i++) {
                if (itemArray[i] != null && itemArray[i].data != -1) {
                    key = itemArray[i].data;
                    hashval = key % newSize;
                    while (newArray[hashval] != null) {
                        hashval++;
                        hashval %= newSize;
                    }
                    newArray[hashval] = itemArray[i];
                }
            }
            // 赋值
            itemArray = newArray;
            size = newSize;
        }

        private int reSize(int size) {
            int nsize = 2 * size + 1;
            while (true) {
                if (isPrime(nsize))
                    return nsize;
                else
                    nsize++;
            }
        }

        private boolean isPrime(int nsize) {
            for (int j = 2; j * j <= nsize; j++)
                if (nsize % j == 0)
                    return false;
            return true;
        }

        public static void main(String[] args) {
            int size = 23;
            LHashFind hash = new LHashFind(size);
            Random rand = new Random();
            for (int i = 0; i < 10; i++) {
                hash.insert(rand.nextInt(1000) + 1);
            }
            hash.display();
            hash.reHash();
            hash.display();
        }
    }

    2,二次探测:寻找和插入都是在起始下标的1,4,9,16……位置后寻找数据或将数据插入空白单元,即步长是按平方增大的,有可能超过整型范围。克服了方法1的大片聚集,但是仍然会产生二次聚集,这个问题不大。

    3,再哈希法:通过给不同关键字设置不同步长解决数据项聚集的问题,开放地址法中常使用此方法。


    import java.util.Random;

    class DataItem {
        int data;

        public DataItem(int data) {
            this.data = data;
        }
    }

    public class ReHash {
        private DataItem[] itemArray;
        private int size;
        private DataItem nonItem;

        public ReHash(int size) {
            this.size = size;
            itemArray = new DataItem[size];
            nonItem = new DataItem(-1);
        }

        private int hashfunc1(int key) {
            return key % size;
        }

        // 对于不同的key,采用不同的步长,这里的5可以换成其他素数
        private int hashfunc2(int key) {
            return 5 - key % 5;
        }

        public void insert(int key) {
            int hashval = hashfunc1(key);
            int stepsize = hashfunc2(key);
            while (itemArray[hashval] != null && itemArray[hashval].data != -1) {
                hashval += stepsize;
                hashval %= size;
            }
            itemArray[hashval] = new DataItem(key);
        }

        public DataItem find(int key) {
            int hashval = hashfunc1(key);
            int stepsize = hashfunc2(key);
            while (itemArray[hashval] != null) {
                if (itemArray[hashval].data == key)
                    return itemArray[hashval];
                hashval += stepsize;
                hashval %= size;
            }
            return null;
        }

        public DataItem delete(int key) {
            int hashval = hashfunc1(key);
            int stepsize = hashfunc2(key);
            while (itemArray[hashval] != null) {
                if (itemArray[hashval].data == key) {
                    DataItem temp = itemArray[hashval];
                    itemArray[hashval] = nonItem;
                    return temp;
                }
                hashval += stepsize;
                hashval %= size;
            }
            return null;
        }

        public void display() {
            for (int i = 0; i < size; i++)
                if (itemArray[i] != null)
                    System.out.print(itemArray[i].data + " ");
                else
                    System.out.print("* ");
            System.out.println();
        }

        public static void main(String[] args) {
            Random rand = new Random();
            int size = 23, n = 20;
            int[] array = new int[n];
            ReHash hash = new ReHash(size);
            for (int i = 0; i < n; i++)
                array[i] = rand.nextInt(1000) + 1;
            for (int key : array)
                hash.insert(key);
            hash.display();
            System.out.println(hash.find(array[5]).data);
            hash.delete(array[5]);
            hash.display();
        }
    }



    展开全文
  • 一个关键字会映射到同一个位桶中的情况,这种情况就就叫做哈希冲突,解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。 一、拉链法 ...

    上篇博客我们说到了,什么是哈希冲突,其实就是再采用哈希函数对输入域进行映射到哈希表的时候,因为哈希表的位桶的数目远小于输入域的关键字的个数,所以,对于输入域的关键字来说,很可能会产生这样一种情况,也就是,一个关键字会映射到同一个位桶中的情况,这种情况就就叫做哈希冲突,解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。

    一、拉链法

    上篇博文我们举的例子,HashMap,HashSet其实都是采用的拉链法来解决哈希冲突的,就是在每个位桶实现的时候,我们采用链表(jdk1.8之后采用链表+红黑树)的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)。首先来看使用拉链法解决哈希冲突的几个操作:

    ①插入操作:在发生哈希冲突的时候,我们输入域的关键字去映射到位桶(实际上是实现位桶的这个数据结构,链表或者红黑树)中去的时候,我们先检查带插入元素x是否出现在表中,很明显,这个查找所用的次数不会超过装载因子(n/m:n为输入域的关键字个数,m为位桶的数目),它是个常数,所以插入操作的最坏时间复杂度为O(1)的。

    ②查询操作:和①一样,在发生哈希冲突的时候,我们去检索的时间复杂度不会超过装载因子,也就是检索数据的时间复杂度也是O(1)的

    ③删除操作:如果在拉链法中我们想要使用链表这种数据结构来实现位桶,那么这个链表一定是双向链表,因为在删除一个元素x的时候,需要更改x的前驱元素的next指针的属性,把x从链表中删除。这个操作的时间复杂度也是O(1)的。

     

    拉链法的优点

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

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

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

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

    ④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

     

    拉链法的缺点

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

    使用例子:

    HashMap

    二、开发地址法

    开放地址法有个非常关键的特征,就是所有输入的元素全部存放在哈希表里,也就是说,位桶的实现是不需要任何的链表来实现的,换句话说,也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候,先通过哈希函数进行判断,若是发生哈希冲突,就以当前地址为基准,根据再寻址的方法(探查序列),去寻找下一个地址,若发生冲突再去寻找,直至找到一个为空的地址为止。所以这种方法又称为再散列法。

    有几种常用的探查序列的方法:

    ①线性探查

    dii=1,2,3,…,m-1;这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

    (使用例子:ThreadLocal里面的ThreadLocalMap)

    ②二次探查

    di=12,-12,22,-22,…,k2,-k2    ( k<=m/2 );这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

    ③ 伪随机探测

    di=伪随机数序列;具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),生成一个位随机序列,并给定一个随机数做起点,每次去加上这个伪随机数++就可以了。

    三、再哈希法

    再哈希法其实很简单,就是再使用哈希函数去散列一个输入的时候,输出是同一个位置就再次哈希,直至不发生冲突位置

    缺点:每次冲突都要重新哈希,计算时间增加。

    展开全文
  • 下面我们用代码来模拟一下这个使用开发地址法解决hash冲突的问题,首先定义一个对象,这里为Info,为了更接近真实场景,我们这里的属性都为字符串, 什么是开放地址法呢? ** 当冲突发生的时候,通过查找数组的一个...
  • 开放地址法哈希表构建,使用纯C语言实现,利用了泛型的思想进行编写。
  • 开放地址法解决哈希冲突 线性开放地址法 线性开放地址法就是在hash之后,当发现在位置上已经存在了一个变量之后,放到它下一个位置,假如下一个位置也冲突,则继续向下,依次类推,直到找到没有变量的位置,放进去...
  • 哈希表-开放地址法之线性探测

    千次阅读 2017-12-19 21:34:57
    哈希表-开放地址法之线性探测
  • 1 开放地址法  这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:  H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,...
  • 数据结构算法\哈希表开放地址法解决冲突
  • 开放地址法 1、Hash函数 Hash函数就是将任意长度的输入转化成固定长度的输出的一类函数 举例说明 比如说我的输入是任意一个自然数(0,1,2,3…),而我要求经过一个函数后我的输出的数的范围要在0-9这样一个范围...
  • 哈希表-开放地址法(二次探测以及在哈希法)
  • C语言实现哈希表(开放地址法

    千次阅读 2019-11-26 20:58:59
    这篇博客介绍的是开放地址法构造的哈希表 哈希表原理可以参考这篇文章:哈希表原理介绍 如果要参考拉链法构造的哈希表,请参考这篇文章:C语言实现哈希表(拉链法) 结构体说明 typedef struct element { int key; ...
  • 所谓的开放定址就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。 公式为: fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1) 用开放定址解决冲突...
  • 开放地址法 这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述: H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ...
  • 开放地址法:容易产生堆积问题;不适于大规模的数据存储;散列函数的设计对冲突会有很大的影响;插入时可能会出现多次冲突的现象,删除的元素是多个冲突元素中的一个,需要对后面的元素作处理,实现较复杂;结点规模...
  • 散列表-开放地址法

    千次阅读 2010-08-12 22:14:00
    散列表的查找过程和建表过程相似。假设给定的值为K,根据建表时设定的散列函数h,计算出散列地址h(K),若表中该地址单元为空,则查找失败;...(1)开放地址法一般形式的函数表示  int Hash(KeyType
  • 什么是Hash冲突 由于Hash原理是将输入空间的值映射到Hash空间内,但Hash值的空间远远小于输入的空间。根据鸽巢原理,一定会存在不同输入被映射成相同输出的过程,这种情况...其中一种简单的表述为: 若有n个笼子...
  • Hash 哈希表 (开放地址法解决冲突) Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也...
  •  * 用开放地址法中的线性探查法解决冲突实现哈希表的运算。  */ public class MyHashSearch {  public static final int SIZE = 10;  public static final int NULLKEY = -1;  public sta
  • 哈希表-开放地址法之线性探测代码(JAVA)import java.io.*;class DataItem { // 数据 private int iData; // data item (key) public DataItem(int ii) { iData = ii; } public int getKey...
  • (3)开放定址为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链中可取α≥1,且结点较大时,拉链中增加的指针域可忽略不计,因此节省空间; (4)在用拉链构造的散列表中...
  • 地址法 建立公共溢出区 优缺点 开放散列(open hashing)/ 拉链法(针对桶链结构) 封闭散列(closed hashing)/ 开放定址法 通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免冲突,因此...
  • Hi=(H(key)+di) MOD m i=1,2,...,k(k 如果di值可能为1,2的平方,3的平方,...,称... * 哈希表的开放地址法中的二次探测  */ package com.eleven; public class HashDoubleApp{  public static void main(Stri
  • 基本定义散列技术是在记录的存储位置和它的关键字之间建立一个确定的...关键字对应的存储位置称为散列地址。散列技术最适合的求解问题是查找与给定值相等的记录。 如果碰到两个不同的关键字key1≠key2key_1 \neq key

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 48,518
精华内容 19,407
关键字:

开放地址法