简介
散列表（也称哈希表），是根据关键码值(key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表
- 它可以快速的进行插入、查找、删除操作，无论数据量有多大，它都能把插入、查找和删除操作的时间复杂度降为O(1)级别
- 基于数组+链表进行实现，当哈希表中存储的数据过多时，需要扩展哈希表数组的长度，但是哈希表的扩展是一个费时的过程
哈希表的结构可以使用数组+链表实现，也可以使用数组+二叉树。如下图的数组+链表实现
散列算法
如果知道一个数组的元素的索引，那么就可以通过索引获得元素。因此，如果能够将 key 对象与索引建立起一一对应的关系，那么就可以通过 key 对应的索引快速找到 value 值了，这个 key 对象转化为索引的算法就是哈希算法，这个索引叫做哈希码（散列码）
- 例子：如果输入的数字是整数，那么合理的方法就是散列函数是 f(x)= x % tablesize。其中 x 是数值，而 tablesize 则是整个表的大小
哈希码冲突
如果能够将 key 对象与索引建立起一一对应的关系，那么就可以通过 key 对应的索引快速找到 value 值了，这个 key 对象转化为索引的算法就是哈希算法，这个索引叫做哈希码（散列码）。如果存在有两个 key 对应的哈希码相同，而数组每个下标只能存放单个元素，此时就出现了哈希码冲突问题
解决冲突方法
- 分离链接法
- 开放寻址法
代码实现
采用数组加链表的形式实现哈希表–即分离链接法
为了方便计算 key 的哈希码，此处的哈希表实现中 key 的值为 int类型，而 value 则是泛型。实现<k,v>的插入、查找、删除操作，以及哈希表的拓展
实现思路
- 创建 Data 类，实现存放 key 和 value
- 包含 key 和 value
- 创建节点类
- 包含 data域 和 next域
- 创建哈希表类
- 创建增、删、查、扩展等方法
public class Data<V> {
private final int key;
private V value;
public Data(int key,V value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}public class Node<V> {
private Data<V> data;
private Node<V> next;
public Node(Data<V> data) {
this.data = data;
}
public Node(int key,V value) {
this.data = new Data<>(key, value);
}
public Node(Data<V> data, Node<V> next) {
this.data = data;
this.next = next;
}
public Data<V> getData() {
return data;
}
public void setData(Data<V> data) {
this.data = data;
}
public Node<V> getNext() {
return next;
}
public void setNext(Node<V> next) {
this.next = next;
}
}public class HashMap<V> {
/**
* 存放链表的数组
*/
private Node<V>[] elements;
/**
* 哈希表中元素个数
*/
private long count;
@SuppressWarnings({"unchecked"})
public HashMap() {
this.count = 0;
this.elements = (Node<V>[]) new Node[10];
}
@SuppressWarnings({"unchecked"})
public HashMap(int maxSize) {
this.count = 0;
this.elements = (Node<V>[]) new Node[maxSize];
}
/**
* 添加一个新的<k,v>到哈希表中，考虑重复的key替换value
* @param key
* @param value
*/
public void put(int key, V value) {
//获取key对应的hash值
int index = hash(key);
Node<V> node = new Node<>(key, value);
//获取哈希表下标为index的链表
Node<V> element = elements[index];
//遍历查找是否存在相同的key，存在则替换value
while (element != null) {
if (element.getData().getKey() == key) {
element.getData().setValue(value);
return;
}
element = element.getNext();
}
//不存在相同的key，直接在链表的头部添加结点
node.setNext(elements[index]);
elements[index] = node;
this.count++;
//当元素数目大于哈希表大小的2倍时，哈希表扩容
if (this.count > this.elements.length * 2L) {
resize();
}
}
/**
* 根据key获取value
* @param key
* @return
*/
public V getValue(int key) {
//获取key对应的hash值
int index = hash(key);
Node<V> element = this.elements[index];
while (element != null) {
if (element.getData().getKey() == key) {
return element.getData().getValue();
}
element = element.getNext();
}
return null;
}
/**
* 根据key移除哈希表的值，存在key移除后返回true，否则返回false
* @param key
* @return
*/
public boolean remove(int key) {
//获取key对应的hash值
int index = hash(key);
Node<V> element = elements[index];
if (element == null) {
return false;
}
if (element.getData().getKey() == key) {
//移除的key为头结点时
elements[index] = element.getNext();
count--;
return true;
} else {
//编译哈希表下标为index的链表，将节点为key的上一个结点指向key的结点下一个
Node<V> pre = element;
element = element.getNext();
while (element != null) {
if (element.getData().getKey() == key) {
pre.setNext(element.getNext());
count--;
return true;
}
element = element.getNext();
}
}
return false;
}
/**
* 将哈希表的数组长度扩展为原来的2倍，将原数组中的所有节点逐个插入到新数组中
*/
@SuppressWarnings({"unchecked"})
private void resize() {
Node<V>[] nodeTemp = (Node<V>[]) new Node[elements.length * 2];
for (Node<V> vNode : elements) {
Node<V> element = vNode;
while (element != null) {
int hash = hash(element.getData().getKey());
Node<V> node = new Node<V>(element.getData());
node.setNext(nodeTemp[hash]);
nodeTemp[hash] = node;
element = element.getNext();
}
}
elements = nodeTemp;
}
/**
* 获取哈希表中元素个数
*/
public long getCount() {
return count;
}
/**
* 获取哈希表长度
*/
public int getHashLength() {
return elements.length;
}
/**
* 获取key的hash值
*/
final int hash(int key) {
//此处简单处理key的hash值
return key % elements.length;
}
}原创文章，作者：，如若转载，请注明出处：https://blog.ytso.com/278370.html