【数据结构】哈希表


class HashBuck{
    static class Node{
        public int key;
        public int val;
        public Node next;
        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;
    public int usedSize; // 已经存放的元素的个数
    public HashBuck(){
        this.array = new Node[4];
    }
    public int get(int key){
        // 找位置
        int index = key % array.length;
        // 遍历当前index下标的链表
        Node cur = array[index];
        while (cur!= null){
            if(cur.key == key){
                return cur.val;
            }else{
                cur = cur.next;
            }
        }
        return -1;  // 找不到的情况
 
    }
    // 采用尾插法
    public void put(int key,int value){
        // 先计算下标
        int index = key % array.length;
        Node node = new Node(key,value);
        Node cur = array[index];
        Node pre = null;
        // 判断index下标是否有值
        if(cur == null){
            array[index] = node;
        }else{
            // 遍历当前index下标，判断是否有相同key
            while (cur != null) {
                // 遍历的时候判断，如果key这个位置已经有值，则需要进行覆盖
                if(cur.key == key){
                    cur.val = value;
                }else{
                    pre = cur;
                    cur = cur.next;
                }
            }
            pre.next = node;
 
        }
        this.usedSize++;
        if(loadFactor() >= 0.75){
            // 扩容的问题：重新哈希 每个下标的每个列表的每个节点
            resize();
        }
    }
    public double loadFactor(){
        return this.usedSize *1.0 /array.length;
    }
    public void resize(){
        Node[] newArray = new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            // 得到i下标的节点
            Node cur = array[i];
            while (cur!= null){
                // 将节点放入新数组的链表时，需要将next置null。为了保证可以遍历，所以需要将cur.next保存下来
                Node curNext = cur.next;
                // 计算在新数组的位置
                int index = cur.key% newArray.length;
                Node curNew = newArray[index];
                // 如果该位置上没有元素，直接放
                if(curNew == null){
                    newArray[index] = cur;
                }else{
                    // 有的话，尾插法
                    while (curNew.next != null){
                        curNew = curNew.next;
                    }
                    curNew.next = cur;
                }
                // 因为节点放到新的链表，所以之前链表的顺序已经不成立，所以需要将cur.next=null
                cur.next = null;
                cur = curNext;
            }
        }
    }
 
}
public class TestDemo {
    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.put(0,11);
        hashBuck.put(1,111);
        hashBuck.put(2,12);
        hashBuck.put(4,13);
        System.out.println(hashBuck);
    }
}

7.2 手动实现HashMap(key的类型是引用类型)

在7.1中，采用的哈希函数是 hash(key) = key%数组长度。如果此时的key不是int，而是String，就不能计算元素的存储位置。将问题总结为：如果key不是int类型，需要将key转为数字，才能使用哈希函数计算位置。

解决方案：Object类的hashcode()方法，可以将传来的对象转为一个合法的数字。

新建一个Student类。假设key是student对象，为了能够将student对象转为数字，Student类需要重写hashcode()函数。在put元素时，涉及到对象的比较，所以需要重写equals方法。


class Student{
    public String id;
    public Student(String id){
        this.id = id;
    }
    @Override
    public int hashCode() {
        return super.hashCode();
    }
 
    @Override
    public boolean equals(Object obj) {
        return super.equals(obj);
    }
}

与7.1中代码不同的是：

使用hashcode()将key转为数字
比较key、value是否相等，采用的是equals方法


public class HashBuck {
    static class Node{
        public K key;
        public V value;
        public Node next;
        public Node(K key,V value){
            this.key = key;
            this.value = value;
        }
 
    }
    public Node[] array = new Node[4];
    public int usedSize;
    public void put(K key,V value){
        // 使用hashcode()将key转为数字
        int hashKey = key.hashCode();
        int index = hashKey % array.length;
        Node node = new Node<>(key,value);
        Node cur = array[index];
        if(cur == null){
            array[index] = node;
        }else{
            while (cur.next != null){
                if(cur.key.equals(key)){
                    cur.value = value;
                    break;
                }
                cur = cur.next;
            }
            cur.next = node;
        }
        this.usedSize++;
        if(loadFactor() >= 0.75){
            resize();;
        }
    }
    public double loadFactor(){
        return this.usedSize *1.0 /array.length;
    }
    public void resize(){
        Node[] newArray = new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            // 得到i下标的节点
            Node cur = array[i];
            while (cur!= null){
                Node curNext = cur.next;
                // 遍历
                int index = (cur.key.hashCode())% newArray.length;
                Node curNew = newArray[index];
                if(curNew == null){
                    newArray[index] = cur;
                }else{
                    while (curNew.next != null){
                        curNew = curNew.next;
                    }
                    curNew.next = cur;
                }
                cur.next = null;
                cur = curNext;
            }
        }
    }
    public V get(K key){
        int index = key.hashCode() % array.length;
        Node cur = array[index];
        while (cur != null){
            if(cur.key.equals(key)){
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }

7.3 hashcode和equals的作用

hashcode：将key转为数字，可以决定该元素存储在数组的哪个位置。

equals：比较元素的key是否相同。

当hashcode结果一样，equals结果一样吗？

不一定。hashcode相同，说明在数组中的存储位置相同，不能证明在哈希桶的位置是否相同。

当equals一样，hashcode结果一样吗？

一样。元素的key一样，肯定存储位置是相同的。所以hashcode一定是一样的。

八、HashMap源码解读

8.1 HashMap的默认容量是16

8.2 HashMap的最大容量：1<<30

8.3 HashMap的容量必须为2的倍数

当容量是2的倍数时，key&(table.length-1) 和key%table.length的结果相同。

8.4 HashMap的默认负载因子是0.75

8.5 HashMap有四种构造方法


// 方法1：传入初始大小和负载因子
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    } 
 
// 方法2：传入初始大小
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
 
// 方法3：不带任何参数
 
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
// 方法4：传入一个Map参数
    public HashMap(Map m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

最常用的是第三种方法。

该方法的初始容量大小是0，第一次put的时候容量大小变成16

8.6 HashMap中的单链表变红黑树的条件

当前链表的长度超过8.并且当前桶的个数大于等于64的时候，才会将当前这个超过8的链表变成红黑树，否则只是2倍扩容。

九、常见的考题

如果 new HashMap(19)，那么 bucket 数组有多大？

32。数组大小必须是2的倍数

HashMap 什么时候开辟 bucket 数组占用内存？

第一次put的时候

HashMap 何时扩容？

计算出的负载因子大于等于默认负载因子

当两个对象的 hashCode 相同时会发生什么？

发生哈希冲突

如果两个键的 hashCode 相同，你如何获取值对象？

遍历当前的链表，通过equals方法确定和查询key一样的key的value

你了解重新调整 HashMap 大小存在什么问题吗？

要进行重新哈希

相关阅读:
Modularized Interaction Network for Named Entity Recognition
Nature、science、cell旗下刊物
 北邮数字系统设计 13 Datapath&Control
Linux下IIC子系统和触摸屏驱动
 新手快速上手IDEA【常用快捷键】
vite脚手架搭建vitepress路径别名设置
 MyBatis篇---第四篇
 简单实现spring的set依赖注入
 代码随想录算法训练营Day55 | 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结篇 | Python | 个人记录向
 Appium切换Android设备输入法, 以及回车按键操作
原文地址：https://blog.csdn.net/weixin_44258092/article/details/126455459