【数据结构】哈希表的原理及实现

/**
 * 哈希表实现
 * @param <K>
 * @param <V>
 */
public class HashTable<K,V> {
    public static void main(String[] args) {
        HashTable<Integer,String> hashTable = new HashTable<>();
        hashTable.put(1,"李祥");
        hashTable.put(2,"张三");
        hashTable.put(3,"李四");
        System.out.println("新增三个元素 ：李祥，张三，李四");
        System.out.println("打印当前哈希表：");
        hashTable.show();
        System.out.println("获取key为3的元素value："+ hashTable.get(3));
        System.out.println("修改key为3的元素value为 小李 ：");
        hashTable.put(3,"小李");
        System.out.println("打印当前哈希表：");
        hashTable.show();
        System.out.println("删除key为2的元素：");
        hashTable.remove(2);
        hashTable.show();
    }
    /**
     * 定义链表数组
     */
    private final LinkedList<K,V>[] linkedArr;
    /**
     * 默认数组长度
     */
    private final static int DEFAULT_LENGTH = 10;
    /**
     * 定义数组的容量
     */
    public int maxSize;
    /**
     * 构造方法初始化
     */
    public HashTable(){
        //定义数组的最大长度
        this.maxSize = DEFAULT_LENGTH;
        //初始化数组
        linkedArr = (LinkedList<K,V>[]) new LinkedList[maxSize];
        //对数组中的每一条链表都要初始化
        for(int i=0;i<maxSize;i++){
            linkedArr[i]=new LinkedList<>();
        }
    }
    /**
     * put 元素
     * @param key
     * @param value
     */
    public void put(K key,V value){
        //key取hashcode根据数组长度取余获取index
        int hashCode = key.hashCode();
        int index =(hashCode % maxSize);
        //把对应的课程 插入到对应的哈希表
        Node<K, V> oldNode = linkedArr[index].get(key);
        //如果当前key 不存在 则表示新增，如果key存在表示替换原有的value
        if(oldNode==null){
            //创建Node节点
            Node<K,V> node = new Node<>(key,value);
            linkedArr[index].add(node);
        }else{
            linkedArr[index].update(key,value);
        }
    }
    /**
     * 根据key值获取value
     * @param key
     * @return
     */
    public V get(K key){
        //获取数组的index
        int hashCode = key.hashCode();
        int index =(hashCode % maxSize);
        //链表中查找key对应的value
        Node<K, V> node = linkedArr[index].get(key);
        return node.value;
    }
    /**
     * 根据key值获取value
     * @param key
     * @return
     */
    public void remove(K key){
        //获取数组的index
        int hashCode = key.hashCode();
        int index =(hashCode % maxSize);
        //链表中查找key对应的value
        linkedArr[index].remove(key);
    }
    /**
     * 输出当前哈希表中的所有元素
     */
    public void show(){
        List<String> showStr = new ArrayList<>();
        for (int i = 0; i < linkedArr.length; i++) {
            List<Node<K, V>> list = linkedArr[i].list();
            for (Node<K, V> node : list) {
                String strNode = "{key="+node.key+",value="+node.value+"}";
                showStr.add(strNode);
            }
        }
        System.out.println("["+String.join(",",showStr)+"]");
    }
    /**
     * 链表存储数据
     * @param <K>
     * @param <V>
     */
    class LinkedList<K,V>{
        /**
         * 定义头节点
         */
        private Node<K,V> head;
        /**
         * 链表中增加数据
         * @param course
         */
        public void add(Node<K,V> data){
            //如果说 head==null  把第一个元素加进去
            if(head==null){
                head=data;
                return;
            }
            // 遍历添加
            Node<K,V> cur=head;
            while (cur.next != null) {
                //跳出循环的条件
                //找到最后一个节点
                cur = cur.next;
            }
            cur.next=data;
        }
        /**
         * 获取链表中全部数据
         */
        public List<Node<K,V>> list(){
            List<Node<K,V>> nodeList = new ArrayList<>();
            if(head==null){
                return nodeList;
            }
            //获取每一项加入到集合中
            Node<K,V> cur=head;
            while (true){
                nodeList.add(cur);
                if(cur.next==null){
                    break;
                }
                cur=cur.next;
            }
            return nodeList;
        }
        /**
         * 根据key 获取对应的node
         * @param key
         * @return
         */
        public Node<K,V> get(K key){
            if(head==null){
                return null;
            }
            //链表有课程 遍历输出 创建一个辅助指针
            Node<K,V> cur=head;
            while (!cur.key.equals(key)) {
                cur = cur.next;
            }
            return cur;
        }
        /**
         * 修改链表中的对应key的值
         * @param key
         * @param value
         */
        public void update(K key, V value) {
            //如果说 head==null,直接返回
            if(head==null){
                return;
            }
            //添加的不是第一门课程 遍历添加
            Node<K,V> cur=head;
            do {
                if(cur.key.equals(key)){
                    cur.value = value;
                    break;
                }
                cur = cur.next;
            }while(cur.next != null);
        }
        /**
         * 删除对应key的node
         * @param key
         * @return
         */
        public void remove(K key) {
            //如果说 head==null,直接返回
            if(head==null){
                return;
            }
            //遍历查找到对应key的node节点
            int x = 0;
            Node<K,V> cur = head;
            while(cur != null) {
                x++;
                if(cur.key.equals(key)){
                    break;
                }
                cur = cur.next;
            }
            //当 cur 为空或这cur.next为空时
            if(cur==null||cur.next==null){
                //判断寻找节点是不是只有一个元素
                if(x == 1){
                    //只有一个元素时，将头节点改成null
                    head = null;
                }else{
                    //当是最后一个元素时，找到当前节点的前一个元素，将前一个元素的next改成null
                    Node<K,V> prev = head;
                    while(prev.next!=null){
                        if (prev.next.key.equals(key)){
                            break;
                        }
                        prev = prev.next;
                    }
                    prev.next=null;
                }
                return;
            }
            cur.key = cur.next.key;
            cur.value = cur.next.value;
            cur.next = cur.next.next;
        }
    }
    class Node<K,V>{
        /**
         * 定义数据
         */
        public V value;
        /**
         * 定义key
         */
        public K key;
        /**
         * 定义下一个节点的
         */
        public Node<K,V> next;
        public Node(K key,V value) {
            this.value = value;
            this.key = key;
        }
    }
}