数据结构与算法–哈希表

简介

散列表（也称哈希表），是根据关键码值(key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表

• 它可以快速的进行插入、查找、删除操作，无论数据量有多大，它都能把插入、查找和删除操作的时间复杂度降为O(1)级别
  • 基于数组+链表进行实现，当哈希表中存储的数据过多时，需要扩展哈希表数组的长度，但是哈希表的扩展是一个费时的过程

哈希表的结构可以使用数组+链表实现，也可以使用数组+二叉树。如下图的数组+链表实现

散列算法

如果知道一个数组的元素的索引，那么就可以通过索引获得元素。因此，如果能够将 key 对象与索引建立起一一对应的关系，那么就可以通过 key 对应的索引快速找到 value 值了，这个 key 对象转化为索引的算法就是哈希算法，这个索引叫做哈希码（散列码）

• 例子：如果输入的数字是整数，那么合理的方法就是散列函数是 f(x)= x % tablesize。其中 x 是数值，而 tablesize 则是整个表的大小

哈希码冲突

如果能够将 key 对象与索引建立起一一对应的关系，那么就可以通过 key 对应的索引快速找到 value 值了，这个 key 对象转化为索引的算法就是哈希算法，这个索引叫做哈希码（散列码）。如果存在有两个 key 对应的哈希码相同，而数组每个下标只能存放单个元素，此时就出现了哈希码冲突问题

解决冲突方法

• 分离链接法
• 开放寻址法

代码实现

采用数组加链表的形式实现哈希表–即分离链接法

为了方便计算 key 的哈希码，此处的哈希表实现中 key 的值为 int类型，而 value 则是泛型。实现<k,v>的插入、查找、删除操作，以及哈希表的拓展

实现思路

1. 创建 Data 类，实现存放 key 和 value
   1. 包含 key 和 value
2. 创建节点类
   1. 包含 data域 和 next域
3. 创建哈希表类
   1. 创建增、删、查、扩展等方法

public class Data<V> {

    private final int key;
    private V value;

    public Data(int key,V value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }
}

public class Node<V> {

    private Data<V> data;
    private Node<V> next;

    public Node(Data<V> data) {
        this.data = data;
    }

    public Node(int key,V value) {
        this.data = new Data<>(key, value);
    }

    public Node(Data<V> data, Node<V> next) {
        this.data = data;
        this.next = next;
    }

    public Data<V> getData() {
        return data;
    }

    public void setData(Data<V> data) {
        this.data = data;
    }

    public Node<V> getNext() {
        return next;
    }

    public void setNext(Node<V> next) {
        this.next = next;
    }
}

public class HashMap<V> {
    /**
     * 存放链表的数组
     */
    private Node<V>[] elements;

    /**
     * 哈希表中元素个数
     */
    private long count;

    @SuppressWarnings({"unchecked"})
    public HashMap() {
        this.count = 0;
        this.elements = (Node<V>[]) new Node[10];
    }

    @SuppressWarnings({"unchecked"})
    public HashMap(int maxSize) {
        this.count = 0;
        this.elements = (Node<V>[]) new Node[maxSize];
    }

    /**
     * 添加一个新的<k,v>到哈希表中，考虑重复的key替换value
     * @param key
     * @param value
     */
    public void put(int key, V value) {

        //获取key对应的hash值
        int index = hash(key);
        Node<V> node = new Node<>(key, value);

        //获取哈希表下标为index的链表
        Node<V> element = elements[index];

        //遍历查找是否存在相同的key，存在则替换value
        while (element != null) {
            if (element.getData().getKey() == key) {
                element.getData().setValue(value);
                return;
            }
            element = element.getNext();
        }

        //不存在相同的key，直接在链表的头部添加结点
        node.setNext(elements[index]);
        elements[index] = node;
        this.count++;

        //当元素数目大于哈希表大小的2倍时，哈希表扩容
        if (this.count > this.elements.length * 2L) {
            resize();
        }
    }

    /**
     * 根据key获取value
     * @param key
     * @return
     */
    public V getValue(int key) {

        //获取key对应的hash值
        int index = hash(key);
        Node<V> element = this.elements[index];
        while (element != null) {
            if (element.getData().getKey() == key) {
                return element.getData().getValue();
            }

            element = element.getNext();
        }

        return null;
    }

    /**
     * 根据key移除哈希表的值，存在key移除后返回true，否则返回false
     * @param key
     * @return
     */
    public boolean remove(int key) {

        //获取key对应的hash值
        int index = hash(key);
        Node<V> element = elements[index];
        if (element == null) {
            return false;
        }

        if (element.getData().getKey() == key) {
            //移除的key为头结点时
            elements[index] = element.getNext();
            count--;
            return true;
        } else {

            //编译哈希表下标为index的链表，将节点为key的上一个结点指向key的结点下一个
            Node<V> pre = element;
            element = element.getNext();
            while (element != null) {
                if (element.getData().getKey() == key) {
                    pre.setNext(element.getNext());
                    count--;
                    return true;
                }

                element = element.getNext();
            }
        }

        return false;
    }

    /**
     * 将哈希表的数组长度扩展为原来的2倍，将原数组中的所有节点逐个插入到新数组中
     */
    @SuppressWarnings({"unchecked"})
    private void resize() {
        Node<V>[] nodeTemp = (Node<V>[]) new Node[elements.length * 2];
        for (Node<V> vNode : elements) {
            Node<V> element = vNode;
            while (element != null) {
                int hash = hash(element.getData().getKey());
                Node<V> node = new Node<V>(element.getData());
                node.setNext(nodeTemp[hash]);
                nodeTemp[hash] = node;
                element = element.getNext();
            }
        }

        elements = nodeTemp;
    }

    /**
     * 获取哈希表中元素个数
     */
    public long getCount() {
        return count;
    }

    /**
     * 获取哈希表长度
     */
    public int getHashLength() {
        return elements.length;
    }

    /**
     * 获取key的hash值
     */
    final int hash(int key) {
        //此处简单处理key的hash值
        return key % elements.length;
    }
}