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 <K,V> implements Map<K,V>{    // 申明一个ENTRY数组用于寄存元素    private Entry<K,V>[] 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<K, V> 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<K, V> 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<K, V>[] oldEntries = Arrays.copyOf(this.entries, capacity);        entries = new Entry[capacity];        for (Entry<K, V> 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<K, V> 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<K, V> 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,V> {        K key;        V value;        public Entry(K key, V value) {            this.key = key;            this.value = value;        }        Entry<K,V> next;    }}