Java 哈希表

目录

1.概念

1.1 原理

1.2 哈希函数

1.3 冲突-解决-负载因子

2.哈希表的实现

2.1 定义节点类以及字段

2.2 新增元素

2.3 获取与key对应的value值

2.4 总代码

---

1.概念

1.1 原理

哈希表是一种时间复杂度只有O(1)的查找数据结构

原理(个人理解):取出一块内存,将插入的数据按照某种函数(哈希函数)去计算,得到一个内存地址,然后将数据存放到该地址,再取出时,可以根据这个函数直接找到该地址的数据

哈希表的难点主要为以下两点:

(1)设计哈希函数

(2)解决哈希冲突

1.2 哈希函数

一个好的哈希表,一定要对应一个好的哈希函数.

哈希函数的设置主要遵循以下几个条件:

(1)函数的结果要在可取空间范围内,并且计算的结果可以取到空间内的任意一块地址

(2)哈希函数计算出来的地址应均匀分布在空间内

常用的哈希函数:

(1)直接定制法: 比如 hash = A*key + B

(2)除留余数法:比如 hash = key % M(M要小于最大可取空间)

1.3 冲突-解决-负载因子

无论哈希函数设计的多么巧妙,发生冲突也是不可避免的(同一块地址,有两个数据符合),这个时候就要去解决冲突.

解决冲突的方法主要为闭散列和开散列

闭散列的方法为:

将冲突的元素放在其解析地址的后一个地址,或者通过一个函数去进行二次计算,相对于开散列比较简单

我们这里主要描述 开散列 也是java库中的使用方法

开散列(也叫链地址法):

将每块地址都设置成一个链表,当发生冲突时,将其进行 头插或者尾插 用来解决冲突问题

但是这样会导致效率的下降,所以需要不断的去扩容调节数组的容量(用数组实现的哈希表)

我们设置一个负载因子n,n = 存储数据个数/数组长度

假设我们设置的负载因子峰值为0.75,那么当实际的计算结果高于这个峰值时就要进行扩容操作,降低冲突发生的概率

2.哈希表的实现

2.1 定义节点类以及字段

    private static class Node {
        private int key;
        private int value;
        Node next;
 
 
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private Node[]  array;
    private int size;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;//负载因子最大值
    private static final int DEFAULT_SIZE = 8;//默认桶的大小
 
    public HashBucket() {
        array = new Node[DEFAULT_SIZE];
    }

2.2 新增元素

这里使用的哈希函数方法为除留余数法.

新增/更新:

首先通过哈希函数找到与插入元素相匹配的链表

然后查找该链表中是否有与插入的节点的key相同的节点,如果有则只更新该节点的values值

若没有相同的key,则进行下一步,将新节点用头插法插入该链表

最后对哈希表进行负载因子的判断,如果表中的负载因子大于设置的最大值,则对链表进行扩容.

扩容:

首先创建一个新的节点数组,长度为原数组的2倍

然后将原数组的每个节点,重新插入新数组

最后将新数组赋给原数组

    //新增
    public void put(int key, int value) {
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if(cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        Node node = new Node(key,value);
        node.next = array[index];
        array[index] = node;
        size++;
        if(loadFactor() >= 0.75) {
            resize();
        }
    }
 
    //判断负载因子是否 达到/超过 最大值
    private double loadFactor() {
        return size * 1.0 / array.length;
    }
 
    //扩容
    private void resize() {
        Node[] newArray = new Node[array.length * 2];
        for(int i = 0;i < array.length;i++) {
            Node cur = array[i];
            while(cur != null) {
                Node curNext = cur.next;
                int index = cur.key % newArray.length;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        array = newArray;
    }

2.3 获取与key对应的value值

首先用哈希函数对key进行判断,找到相对应的链表

然后寻找与key相对应的节点,最后返回value

如果没有则返回-1

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

2.4 总代码

public class HashBucket {
    private static class Node {
        private int key;
        private int value;
        Node next;
 
 
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
 
 
    private Node[]  array;
    private int size;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    private static final int DEFAULT_SIZE = 8;//默认桶的大小
 
    public HashBucket() {
        array = new Node[DEFAULT_SIZE];
    }
    public void put(int key, int value) {
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if(cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        Node node = new Node(key,value);
        node.next = array[index];
        array[index] = node;
        size++;
        if(loadFactor() >= 0.75) {
            resize();
        }
    }
 
    //扩容
    private void resize() {
        Node[] newArray = new Node[array.length * 2];
        for(int i = 0;i < array.length;i++) {
            Node cur = array[i];
            while(cur != null) {
                Node curNext = cur.next;
                int index = cur.key % newArray.length;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        array = newArray;
    }
 
 
    private double loadFactor() {
        return size * 1.0 / array.length;
    }
 
 
    public int get(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if(cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }
}