目录

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;}
}