[数据结构与算法]2021-07-26hashmap的的实现

节点

public class Node<T, V> {
    T key;
    V value;
    Node<T, V> next;

    public Node(T key, V value) {
        this.key=key;
        this.value = value;
    }

    public Node() {
    }
}

链表

package shoudongshixianHashMap;

public class Link<T, V> {

    private Node<T, V> head;

    public Link(Node<T, V> node) {
        this.head = node;
        head.next = null;
    }

    public Link() {
        this(new Node<>());
    }

    /**
     * 插入一个键值对，如果该节点的键和其他节点键重复，则覆盖值。
     * @param key 键
     * @param value 值
     */
    public void insert(T key, V value) {
        Node<T, V> tempNode = find(key);
        if (tempNode != null) {
            tempNode.value = value;
        } else {
            Node<T, V> node = new Node<>(key, value);
            node.next = head.next;
            head.next = node;
        }
    }

    /**
     * 根据指定key找相应结点
     * @param key 键
     * @return 找到的相应结点
     */
    public Node<T, V> find(T key) {
        Node<T, V> parent = findParent(key);
        if (parent == null) {
            return null;
        } else {
            return parent.next;
        }
    }

    /**
     * 根据指定key删除相应结点
     * @param key 键
     * @return 是否删除成功
     */
    public boolean delete(T key) {
        Node<T, V> parent = findParent(key);
        if (parent == null) {
            return false;
        }
        parent.next = parent.next.next;
        return true;
    }

    /**
     * 更新指定key的值
     * @param key 键
     * @param newValue 新值
     * @return 是否更新成功
     */
    public boolean update(T key, V newValue) {
        Node<T, V> parent = findParent(key);
        if (parent == null) {
            return false;
        }
        parent.next.value = newValue;
        return true;
    }

    /**
     * 根据给定key找到其父节点
     * @param key 键
     * @return 对应的父节点
     */
    private Node<T, V> findParent(T key) {
        if (head == null) {
            return null;
        }

        Node<T, V> node = head.next;
        Node<T, V> parent = head;

        while (node != null) {
            if (node.key == key) {
                return parent;
            }
            parent = node;
            node = node.next;
        }

        return null;
    }

    /**
     * 返回头结点
     * @return 头结点
     */
    public Node<T, V> getHead() {
        return head;
    }
}

表的实现

    public boolean delete(T key) {
        return this.map[getIndex(key)].delete(key);
    }

    public boolean update(T key, V value) {
        return this.map[getIndex(key)].update(key, value);
    }

    public Integer getIndex(T key) {
        return key.hashCode() % size;
    }

    public Link<T, V>[] getMap() {
        return map;
    }
}