【数据结构和算法】——|【数据结构和算法】—— 哈希表
1.什么是哈希表
哈希表是结合哈希算法结合其他数据结构构成的一种数据结构。
为什么会产生这样的数据结构呢？
主要原因是在理想情况下，取出和放入元素所消耗的时间复杂度为
\( O(1) \)
【【数据结构和算法】——|【数据结构和算法】—— 哈希表】比如我们看一种常见的实现方式，哈希算法+数组+链表构成的哈希表：
假设数组index从1开始，那么根据哈希算法，元素1就放在数组下标为1的地方，元素3就放在数组下标为3的地方，元素5放在数组下标为1的地方，但是因为元素1已经在数组中了，对于这种情况，我们的一种解决方式就是元素1和元素5通过链表连接，元素1仍然在数组中，新加入的元素5放在元素1后面，元素1的next节点指向元素5.
文章图片
2. java实现
哈希表的用途很广，比如java的HashMap、HashSet。
对于哈希表，我们的操作主要是PUT和GET操作。
下面就来看看怎么实现简易版本的HashMap。
import java.util.Arrays;
import java.util.Objects;
/**
* key and value are not permitted null
* @author bennetty74
* @since 2021.10.24
*/
public class HashMap implements Map{
// 声明一个ENTRY数组用于存放元素
private Entry[] entries;
private final double loadFactor = 0.75d;
private int capacity = 8;
private int size = 0;
@SuppressWarnings("unchecked")
public HashMap() {
entries = new Entry[this.capacity];
}@SuppressWarnings("unchecked")
public HashMap(int capacity) {
this.capacity = capacity;
entries = new Entry[capacity];
}@Override
public boolean contains(K key) {
int idx = getIndex(key);
if (entries[idx] == null) {
return false;
}
Entry entry = entries[idx];
while (entry != null) {
if (entry.key.equals(key)) {
return true;
}
entry = entry.next;
}
return false;
}
// put操作，不允许key和value为null
public boolean put(K key, V value) {
if (Objects.isNull(key) || Objects.isNull(value)) {
throw new IllegalArgumentException("Key or value is null");
}
int idx = getIndex(key);
// if null, put in entries array
if (Objects.isNull(entries[idx])) {
entries[idx] = new Entry<>(key, value);
} else {
// else put at the head of Entry list
Entry newEntry = new Entry<>(key, value);
newEntry.next = entries[idx];
entries[idx] = newEntry;
}
// if load factor greater than 0.75, then rehash
if (size++ / (double) capacity > 0.75f) {
rehash();
}
return true;
}private void rehash() {
capacity = 2 * capacity;
Entry[] oldEntries = Arrays.copyOf(this.entries, capacity);
entries = new Entry[capacity];
for (Entry oldEntry : oldEntries) {
if (oldEntry != null) {
put(oldEntry.key, oldEntry.value);
}
}
}public V get(K key) {
if (Objects.isNull(key)) {
throw new IllegalArgumentException("Key is null");
}
// get idx by key's hashCode
int idx = getIndex(key);
Entry entry = entries[idx];
if (!Objects.isNull(entry)) {
while (!Objects.isNull(entry)) {
if (key.equals(entry.key)) {
return entry.value;
}
entry = entry.next;
}
}
// not found the specific key, return null
return null;
}
// 此处的hash算法很简单，就是根据key的hashCode除以entry数组的容量的余数作为数组下标存放元素
private int getIndex(K key) {
return key.hashCode() % capacity;
}@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("HashMap { ");
for (int i = 0;
i < capacity;
i++) {
if (entries[i] != null) {
Entry entry = entries[i];
while (entry != null) {
sb.append(entry.key).append("=").append(entry.value).append(",");
entry = entry.next;
}
}
}
sb.replace(sb.length() - 1, sb.length(), "").append(" }");
return sb.toString();
}// Entry类，包含HashMap的key和value
private static class Entry {
K key;
V value;
public Entry(K key, V value) {
this.key = key;
this.value = https://www.it610.com/article/value;
}Entry next;
}} 推荐阅读
- 宽容谁
- 我要做大厨
- 急于表达——往往欲速则不达
- 第三节|第三节 快乐和幸福（12）
- 增长黑客的海盗法则
- 画画吗（）
- 20170612时间和注意力开销记录
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷