HashMap简单实现

import java.util.*;

/**
 * @Author nanfengnan
 * @Date 2022/4/19
 * @Description 自己实现的HashMap
 * 哈希函数:hashCode()+除留余数法
 * 冲突解决:链地址法
 */
public class ThirdHashMap<K, V> {
    /**
     * 链表节点
     * @param <K>
     * @param <V>
     */
    class Node<K,V>{
        private K key;
        private V value;
        private Node<K,V> next;

        public Node(K key,V value){
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
    // 默认容量
    final int DEFAULT_CAPACITY = 16;
    // 负载因子
    final float LOAD_FACTOR = 0.75f;
    // HashMap的大小
    private int size;
    // 桶数组
    Node<K,V>[] buckets;

    /**
     * 两个构造函数,用于初始化桶的大小
     */
    public ThirdHashMap() {
        buckets = new Node[this.DEFAULT_CAPACITY];
        this.size = 0;
    }
    public ThirdHashMap(int capacity) {
        buckets = new Node[capacity];
        this.size = 0;
    }

    /**
     * 哈希函数:采用除留余数法
     * @param key
     * @param length
     * @return 哈希地址
     */
    public int getIndex(K key,int length) {
        // 获取hash code ,32位带符号数
        int hashCode = key.hashCode();
        // 除留余数法
        return Math.abs(hashCode % length);
    }

    /**
     * 得到value方法
     * @param key
     * @return
     */
    public V get(K key) {
        // 获得key的哈希地址
        int index = getIndex(key, buckets.length);
        Node<K, V> node = buckets[index];
        // buckets[index]里面没有数据
        if (node == null)
            return null;
        // 否则遍历链表
        while (node != null) {
            // 考虑字符串使用equals
            if ((node.key.hashCode() == key.hashCode())
                    && (node.key == key || node.key.equals(key))) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    /**
     * put方法
     * @param key
     * @param value
     */
    public void put(K key,V value) {
        // 判断是否超过负载空间
        if (size >= buckets.length*LOAD_FACTOR)
            resize();
        putValue(key,value,buckets);
    }

    /**
     * 得到桶中元素个数
     * @return
     */
    public int size() {
        return this.size;
    }

    /**
     * 删除key
     * @param key
     */
    public Node<K,V> remove(K key) {
        // 得到哈希地址
        int index = getIndex(key, buckets.length);
        if (buckets[index] == null)
            return buckets[index];
        else if ((buckets[index].key.hashCode() == key.hashCode()) 
                && (buckets[index].key == key || buckets[index].key.equals(key))) {
            Node<K,V> t = buckets[index].next;
            buckets[index].next = t.next;
            return t;
        }
        Node<K,V> node = buckets[index].next;
        Node<K,V> pre = node;
        while (node != null) {
            // 找到了key,则断链删除元素
            if ((node.key.hashCode() == key.hashCode())
            && (node.key == key || node.key.equals(key))) {
                pre.next = node.next;
                return node;
            }
            pre = pre.next;
            node = node.next;
        }
        // 否则,桶中没有此元素
        return null;
    }

    /**
     * containsKey
     * @param key
     * @return
     */
    public boolean containsKey(K key) {
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] == null)
                continue;
            Node node = buckets[i];
            while (node != null) {
                if ((node.key.hashCode() == key.hashCode())
                && (node.key == key || node.key.equals(key)))
                    return true;
                node = node.next;
            }
        }
        return false;
    }

    /**
     * containsValue
     * @param value
     * @return
     */
    public boolean containsValue(V value) {
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] == null)
                continue;
            Node node = buckets[i];
            while (node != null) {
                if ((node.value == value || node.value.equals(value)))
                    return true;
                node = node.next;
            }
        }
        return false;
    }
    
    /**
     * 得到keySet
     * @return
     */
    public Set<K> keySet() {
        Set<K> set = new HashSet<K>();
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] == null)
                continue;
            Node<K,V> node = buckets[i];
            while (node != null) {
                set.add(node.key);
                node = node.next;
            }
        }
        return set;
    }

    /**
     * 得到values
     * @return
     */
    public Collection<V> values() {
        Collection<V> collection = new ArrayList<V>();
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] == null)
                continue;
            Node<K,V> node = buckets[i];
            while (node != null) {
                collection.add(node.value);
                node = node.next;
            }
        }
        return collection;
    }

    /**
     * 向桶中添加元素,也可以当作复制元素使用
     * @param key
     * @param value
     * @param table
     */
    public void putValue(K key,V value,Node<K,V>[] table) {
        // 获取哈希地址,判断是否存在
        int index = getIndex(key, table.length);
        // 得到table[index]元素
        Node<K,V> node = table[index];
        // 桶中没有元素
        if (node == null) {
            table[index] = new Node<K, V>(key,value);
            size++;
            return;
        }
        // 冲突,使用链地址法
        while (node != null) {
            // key相同则修改,考虑字符串
            if ((node.key.hashCode() == key.hashCode())
            && (node.key == key || node.key.equals(key))) {
                node.value = value;
            }
            node = node.next;
        }
        // 没有该映射,添加到链表的头部
        Node<K,V> t = new Node<K, V>(key,value);
        t.next = table[index].next;
        table[index].next = t;
        size++;
    }

    /**
     * 扩容函数
     */
    private void resize() {
        // 扩容2倍
        Node<K,V>[] newbuckest = new Node[buckets.length<<1];
        // 将当前元素写入newbuckets桶中
        rehash(newbuckest);
        // buckets指向newbuckets
        buckets = newbuckest;
    }

    /**
     * 将酒桶的元素复制到新的桶中
     * @param newbuckets
     */
    private void rehash(Node<K,V>[] newbuckets) {
        size = 0;
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] == null)
                continue;
            // 复制链表节点
            Node<K,V> node = buckets[i];
            while (node != null) {
                putValue(node.key,node.value,newbuckets);
                node = node.next;
            }
        }
    }
    
}