目录

1，概念

2，冲突-避免

3，冲突-避免-哈希函式设计

4，冲突-避免-负载因子调节?

4，冲突-解决-闭散列

①线性探测

②二次探测

5，冲突-解决-开散列/哈希桶

6，完整代码

1，概念

当向该结构中：

插入元素

根据待插入元素的关键码，以此函式计算出该元素的存盘位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的计算，把求得的函式值当做元素的存盘位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

例如：资料集合{1，7，6，4，5，9}；

哈希函式设定为：hash(key) = key % capacity; capacity为存盘元素底层空间总的大小，

2，冲突-避免

常见哈希函式

直接定制法--(常用)

取关键字的某个线性函式为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关 键字的分布情况 使用场景：适合查找比较小且连续的情况

除留余数法--(常用)

设散串列中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函式： Hash(key) = key% p(p<=m),将关键码转换成哈希地址

平方取中法--(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对 它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分 布，而位数又不是很大的情况

4，冲突-避免-负载因子调节

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以 把key存放到冲突位置中的“下一个” 空位置中去，

①线性探测

插入

通过哈希函式获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到 下一个空位置，插入新元素

线性探测的缺陷是产生冲突的资料堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨 着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为： = ( + )% m, 或者： = ( - )% m，其中：i = 1,2,3…， 是通过散列函式Hash(x)对元素的关键码 key 进行计算得到的位置， m是表的大小， 对于2.1中如果要插入44，产生冲突，使用解决后的情况为：

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函式计算散列地址，具有相同地址的关键码归于同一子 集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存盘在哈希表中，

     static class Node {
         public int key;
         public int val;
         public Node next;

         public Node(int key, int val) {
             this.key = key;
             this.val = val;
         }
     }

     private Node[] array;
     public int usedSize;

     public HashBucket() {
         this.array = new Node[10];
         this.usedSize = 0;
     }

 public void put(int key,int val){
        int index = key % this.array.length;
        Node cur = array[index];
        while (cur != null){
            if(cur.val == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //头插法
         Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        this.usedSize++;
        if(loadFactor() >= 0.75){
            resize();
        }
    }

public int get(int key) {
         //以什么方式存盘的  那就以什么方式取
         int index = key % this.array.length;
         Node cur = array[index];
         while (cur != null) {
             if(cur.key == key) {
                 return cur.val;
             }
             cur = cur.next;
         }
         return -1;//
     }

public void resize(){

        Node[] newArray = new Node[2*this.array.length];
        for (int i = 0; i < this.array.length; i++){
            Node cur = array[i];
            Node curNext = null;
            while (cur != null){

                curNext = cur.next;
                int index = cur.key % newArray.length;
                cur.next = newArray[i];
                newArray[i] = cur;
                cur = curNext.next;
                cur = curNext;

            }
        }
        this.array = newArray;
    }

6，完整代码

 class HashBucket {

     static class Node {
         public int key;
         public int val;
         public Node next;

         public Node(int key, int val) {
             this.key = key;
             this.val = val;
         }
     }

     private Node[] array;
     public int usedSize;

     public HashBucket() {
         this.array = new Node[10];
         this.usedSize = 0;
     }

     public void put(int key,int val) {
         //1、确定下标
         int index = key % this.array.length;
         //2、遍历这个下标的链表
         Node cur = array[index];
         while (cur != null) {
             //更新val
             if(cur.key == key) {
                 cur.val = val;
                 return;
             }
             cur = cur.next;
         }
         //3、cur == null   当前阵列下标的 链表  没要key
         Node node = new Node(key,val);
         node.next = array[index];
         array[index] = node;
         this.usedSize++;
         //4、判断  当前 有没有超过负载因子
         if(loadFactor() >= 0.75) {
             //扩容
             resize();
         }
     }

     public int get(int key) {
         //以什么方式存盘的  那就以什么方式取
         int index = key % this.array.length;
         Node cur = array[index];
         while (cur != null) {
             if(cur.key == key) {
                 return cur.val;
             }
             cur = cur.next;
         }
         return -1;//
     }


     public double loadFactor() {
         return this.usedSize*1.0 / this.array.length;
     }



    public void resize(){

        Node[] newArray = new Node[2*this.array.length];
        for (int i = 0; i < this.array.length; i++){
            Node cur = array[i];
            Node curNext = null;
            while (cur != null){

                curNext = cur.next;
                int index = cur.key % newArray.length;
                cur.next = newArray[i];
                newArray[i] = cur;
                cur = curNext.next;
                cur = curNext;

            }
        }
        this.array = newArray;
    }


}