哈希表(散列表)(Hashing)(顺序存储与链式存储相结合)

import java.util.Objects;

/**
 * @Classname MyHashTable
 * @Description hashtable的增删改查的简单实现
 */
public class MyHashTable<K, V> {
	 private static class Node<K, V> {
	        //key
	        K key;
	        //value
	        V value;
	        //哈希值
	        int hash;
	        //指向后一个结点
	        Node next;

	        public Node() {
	            //hash值只取决于key
	            this.hash = this.key == null ? 0 : this.key.hashCode();
	            this.next = null;
	        }

	        public Node(K key, V value) {
	            this.key = key;
	            this.value = value;
	            this.hash = this.key == null ? 0 : this.key.hashCode();
	            this.next = null;
	        }
	    }
	 
	//数组
    Node<K, V>[] elements;
    //元素个数
    int size;

    //默认容量
    int capacity = 4;
    //填装因子
    double factor = 0.7;

    public MyHashTable() {
        //初始化元素个数
        size = 0;
        //初始化数组 ★★★★★ 记住这个写法！ Node声明为静态泛型内部类
        elements = (Node<K, V>[]) new Node[capacity];
    }

    /**
     * 查
     * @param key
     * @return
     */
    public V get(K key) {
        //先计算下标值
        int index = key.hashCode() % elements.length;
        //对应下标位置找元素
        Node<K, V> node = elements[index];
        while (node != null) {
            if (Objects.equals(key, node.key)) {
                //找到就返回
                return node.value;
            }
            //元素后移
            node = node.next;
        }
        //找不到就返回null
        return null;
    }

    /**
     * 改元素
     *
     * @param key
     * @param value
     */
    public void set(K key, V value) {
        //先计算下标值
        int index = key.hashCode() % elements.length;
        //对应下标位置找元素
        Node<K, V> node = elements[index];
        while (node != null) {
            if (Objects.equals(key, node.key)) {
                //找到就改
                node.value = value;
                //打印修改成功
                System.out.println("修改成功");
                return;
            }
            //元素后移
            node = node.next;
        }
        //找不到就打印没找到
        System.out.println("没找到这个元素");
    }


    /**
     * 删除元素
     *
     * @param key
     */
    public void remove(K key) {
        //先计算下标
        int index = key.hashCode() % elements.length;
        //去下标位置找
        Node<K, V> node = elements[index];
        //父结点
        Node<K, V> f = null;
        while (node != null) {
            //判断key是否相等
            if (Objects.equals(key, node.key)) {
                //只有一个结点
                if (f == null && node.next == null) {
                    elements[index] = null;
                }
                //有多个结点，要删的是头节点
                if (f == null && node.next != null) {
                    elements[index] = node.next;
                }
                //多个结点，但删的是中间结点
                if (f != null && node.next != null) {
                    f.next = node.next;
                }
                //有多个结点，要删的是尾节点
                if (f != null && node.next == null) {
                    f.next = null;
                }
                //打印删除成功
                System.out.println("删除成功");
                size--;
                return;
            }
            //不相等,就往链表后面找
            f = node;
            node = node.next;
        }
        //没找到就打印个没有这个元素
        System.out.println("删除失败，没找到这个元素");
    }

    /**
     * 添加元素
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        //判断数组是否需要扩容
        if (size * 1.0 / elements.length > factor) {
            //扩容
            resize();
        }
        //把新元素放进数组中
        Node<K, V> e = (Node<K, V>) new Node(key, value);
        //根据hash计算下标值
        int index = e.hash % elements.length;
        //判断数组的这个位置是否有元素了
        if (elements[index] == null) {
            //没有元素，直接放
            elements[index] = e;
        } else {
            //有元素，放到链表尾
            Node<K, V> node = elements[index];
            while (node.next != null) {
                node = node.next;
            }
            node.next = e;
        }
        //更新size
        size++;
    }

    /**
     * 扩容数组
     */
    private void resize() {
        //新的capacity为旧的两倍(这里我就不考虑最大限制这些复杂情况了，只是做一个简单的实现)
        int newCapacity = capacity * 2;
        //创建新数组
        Node<K, V>[] newEle = (Node<K, V>[]) new Node[newCapacity];
        //把旧数组中的元素放到新数组中
        //遍历旧数组中的元素
        for (Node e : elements) {
            //如果数组为空，跳过
            if (e == null) continue;
            //根据hash计算下标值
            int index = e.hash % newEle.length;
            //判断数组的这个位置是否有元素了
            if (newEle[index] == null) {
                //没有元素，直接放
                newEle[index] = e;
            } else {
                //有元素，放到链表尾
                Node<K, V> node = newEle[index];
                while (node.next != null) {
                    node = node.next;
                }
                node.next = e;
            }
        }
        //把新数组赋给旧数组
        capacity = newCapacity;
        elements = newEle;
    }
    
    public static void main(String[] args) {
		MyHashTable<Integer, Integer> hash= new MyHashTable<>();
		hash.put(1, 2);
		hash.put(2, 9);
		hash.put(3, 8);
		
		hash.remove(1);
		
		System.out.println(hash.size);
		System.out.println(hash.get(2));
	}
   
}