关于数据结构和算法:数据结构和算法-哈希表

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


}