哈希桶（开散列）

前言

哈希桶用来解决哈希冲突，牺牲空间换取时间。
通过数组和链表来实现哈希桶

 public class Node{
        public int key;
        public int value;
        public Node next;

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

定义初始化数组大小为10；
size定义为数组中的有效个数

  public Node[]arry=new Node[10];
    public int size;

实现插入put方法

实现插入数据put方法
第一步：使用哈希函数（hash(key)=key%储存元素底层空间大小）找到插入值在哈希表中的位置
第二步:判断当前数组下标的链表的key与插入的key相同，相同则更新value（哈希桶插入相同元素覆盖其对应的value值），不同则插入
第三步:进行插入（使用头插法）

负载因子=插入表中的元素个数/列表长度
当负载因子>0.75时要重新扩容数组

*注意不能直接扩容(这里直接扩大一倍) 比如：key=14原来的hash(key)=14%10=4;直接扩容后hash(key)=14/20=14
位置都相同这选择遍历旧数组构建新数组后将新数组置换旧数组来完成扩容

 public void put(int key,int value){
        //找到位置
        int index=key%arry.length;
        //判断当前数组下标的链表的key与插入的key相同，相同则更新value，不同则插入
        Node cur=arry[index];
        while (cur!=null){
            if(cur.key==key){
                cur.value=value;
            }else{
                cur=cur.next;
            }
        }
        //走到这进行插入(使用头插法)
        Node cut=new Node(key,value);
        cut.next=arry[index];
        arry[index]=cut;
        size++;
        double fuzai=size*1.0f/arry.length;//代表负载因子
        if(fuzai>0.75){
            //扩容,不能直接扩
            Knewarry();
        }
    }
    public void Knewarry(){
        Node[]newarry=new Node[arry.length*2];
        for (int i = 0; i <arry.length ; i++){
            Node cur=arry[i];
            while (cur!=null){
                //插入新数组新链表
                int index=cur.key% newarry.length;
                Node curN=cur.next;//防止cur.next丢失
                cur.next=newarry[index];
                newarry[index]=cur;
                cur=curN;
            }
        }
        arry=newarry;
    }

当插入第8个元素时进行扩容注意14位置的转移

实现get方法

得到key对于的value值

 public int get(int key) {
        int index=key%arry.length;
        Node cur=arry[index];
        while (cur!=null){
            if(cur.key==key){
                return cur.value;
            }
            cur=cur.next;
        }
      return -1;
    }

实现泛型类哈希桶

public class HashBucket2<E,V>{
    //使用泛型
    //通过数组和链表来实现
    public class Node<E,V>{
        public E key;
        public V value;
        public Node<E,V> next;

        public Node(E key,V value){
            this.key=key;
            this.value=value;
        }
    }
    public Node<E,V>[]arry=(Node<E,V>[])new Node[10];
    public int size;
    public void put(E key,V value){
        //找到位置
        int hashCode=key.hashCode();
        int index=hashCode%arry.length;
        //判断当前数组下标的链表有没有key相同，相同则更新value，不同则插入
        Node cur=arry[index];
        while (cur!=null){
            if(cur.key.equals(key)){
                cur.value=value;
            }else{
                cur=cur.next;
            }
        }
        //走到这进行插入(使用头插法)
        Node cut=new Node(key,value);
        cut.next=arry[index];
        arry[index]=cut;
        size++;
        double fuzai=size*1.0f/arry.length;//代表负载因子
        if(fuzai>0.75){
            //扩容,不能直接扩
            Knewarry();
        }
    }
    public void Knewarry(){
        Node[]newarry=new Node[arry.length*2];
        for (int i = 0; i <arry.length ; i++){
            Node cur=arry[i];
            while (cur!=null){
                //插入新数组新链表
                int index=hashCode()% newarry.length;
                Node curN=cur.next;//防止cur.next丢失
                cur.next=newarry[index];
                newarry[index]=cur;
                cur=curN;
            }
        }
        arry=newarry;
    }
    public Object get(E key) {
        int hashCode=key.hashCode();
        int index=hashCode%arry.length;
        Node cur=arry[index];
        while (cur!=null){
            if(cur.key.equals(key)){
                return  cur.value;
            }
            cur=cur.next;
        }
        return null;
    }
    public boolean pek(E key,V value){
        int hashCode=key.hashCode();
        int index=hashCode%arry.length;
        Node cur=arry[index];
        while (cur!=null){
            if(cur.key.equals(key)){
                if(cur.value.equals(value)){
                    return true;
                }
            }
            cur=cur.next;
        }
        return false;
    }
}

原文地址：https://blog.csdn.net/2401_85487314/article/details/145283726

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！