数据结构与算法（第一季）：哈希表（Hash Table）

作者: 萧1帅 | 来源:发表于2022-01-06 09:08 被阅读0次

一、哈希表（Hash Table）

1、概念

哈希表也叫做散列表。
哈希表的原理：

image

利用哈希函数生成key对应的index，时间复杂度O(1)。
根据index(索引)操作定位数组元素，时间复杂度O(1)。
哈希表的空间换时间的典型应用。

2、哈希冲突

image

哈希冲突也叫做哈希碰撞。
- 2个不同的key，经过哈希函数计算出相同的结果。
- key1 != key2，hash(key1) = hash(key2)
解决哈希冲突的常见方法
- 按照一定规则（线性探测，平方探测）向其他地址探测，直到遇到空桶。（开放定址法）
- 设计多个哈希函数。（再哈希法）
- 通过链表将同一index的元素串起来。（链地址法）

image

3、JDK1.8的哈希冲突解决方案

image

默认使用单向链表将元素串起来。
当单向链表的节点数量大于8时，将转为红黑树来存储元素。在调整容量时，如果树节点数量小于6，又会转为单向链表。
为什么不使用双向链表，而是单向链表？
- 每次查找都要从单向链表头节点开始遍历，首先确认链表中是否已有该元素，若没有则插入。
- 单向链表比双向链表少一个指针，可以节省内存空间。

4、哈希函数

哈希表中哈希函数的实现步骤：
- 生成key的哈希值（必须是整数）。
- 再让key的哈希值跟数组的大小进行相关运算，生成一个索引值。

image

为了提高效率，可以使用&与运算取代%运算（前提将数组的长度设计为2^n）。

image

因为数组长度为为2^n，转换为二进制是10000或100之类的值，table.length - 1的结果转换成二进制即为01111或011之类的值。
将hash_code(key)和01111做与运算，比如10100&00111，结果为00101，值肯定小于00111，且最小为00000，最大为00111。
结论就是无论hash_code(key)有多大，当它与上table.length - 1，它的值都是在0到table.length - 1之间。
良好的哈希函数是让哈希值更加均匀的分布，减少哈希冲突次数，提升哈希表的性能。

5、如何生成hash_code(key)

key的常见种类可能是有整数，浮点数，字符串，自定义对象。
不同种类的key，哈希值的生成方式不一样，但目标是一致的：
- 尽量让每个key的哈希值是唯一的。
- 尽量让key的所有信息参与运算。

5.1、整数的哈希值

整数的哈希值则直接为它的值，比如10的哈希值就是10。

5.2、浮点数的哈希值

浮点数的哈希值是将存储的二进制格式转为整数值。
比如10.6在内存中是01010010101，那么将01010010101转为整数即为1093245338。

5.2、`Long`和`Double`的哈希值

java中的hash值必须是整数，即是32位。
Long和Double都是64位，可以将value的高32位和低32位混合计算出32位的值，然后再用value的值与这个32位值做亦或运算（相同为0，不同为1）。
亦或运算之后再将64位的结果强制转换为32位。

image

最终获取的值是橙色部分。
这样即充分利用所有信息计算出了哈希值。

5.3、字符串的哈希值

比如字符串jack，由j、a、c、k四个字符组成（字符的本质就是一个整数，因为可以转换成ascII码）
因此jack的哈希值可以表示为j*n^3 + a*n^2 + c*n^1 + k*n^0。

5.4、自定义对象的哈希值

默认情况下，自定义对象的哈希值是跟内存地址有关系的。
所以两个对象即使各个属性值都相同，但他们的哈希值是不同的，如果用一个字典保存这两个对象，字典内会有两个对象。
如何能让字典中只保存相同对象中的一个呢？这就需要我们重写hashCode函数。

image

重写的hashCode函数，我们将对象所有属性都计算进来，这样即充分利用所有信息计算出了哈希值。
当哈希冲突的时候，我们会调用对象的equals函数进行对象间的比较。如果两个对象相同，则覆盖，如果不同，则加入到value链表中。所以我们也需要重写equals函数。
哈希值相同的两个对象，不一定相等，只能说两个对象通过hashCode算出的索引值相同。

5.5、自定义对象存储举例

假设我们创建三个对象存入map中，并且p1和test的哈希值相同：

image

当存入p1和test时，map中的结构如下：

image

当存入p2时，会调用equals函数比较p1和p2

，因为重写了equals函数，所以会返回true，在map中，当确认两个对象相等时，则会执行替换：

image

二、哈希表的接口设计（HashMap）

用Map实现一个哈希表（HashMap）
通过一个数组保存key（索引）。
key对应的value（数据）则直接保存红黑树的根节点。

public class HashMap<K, V> implements Map<K, V> {
    private Node<K, V>[] table;
    protected static class Node<K, V> //声明一个节点类
    private static final int DEFAULT_CAPACITY = 1 << 4; //数组默认长度，16

    public HashMap() {
        table = new Node[DEFAULT_CAPACITY]; //建议长度为2^n
    }
}
复制代码

三、哈希表的实现（HashMap）

1、声明节点

protected static class Node<K, V> {
    int hash;
    K key;
    V value;
    boolean color = RED;
    Node<K, V> left;
    Node<K, V> right;
    Node<K, V> parent;
    public Node(K key, V value, Node<K, V> parent) {
        this.key = key;
        int hash = key == null ? 0 : key.hashCode();
        this.hash = hash ^ (hash >>> 16);
        this.value = value;
        this.parent = parent;
    }

    public boolean hasTwoChildren() {
        return left != null && right != null;
    }

    public boolean isLeftChild() {
        return parent != null && this == parent.left;
    }

    public boolean isRightChild() {
        return parent != null && this == parent.right;
    }

    public Node<K, V> sibling() {
        if (isLeftChild()) { return parent.right; }
        if (isRightChild()) { return parent.left; }
        return null;
    }

    @Override
    public String toString() {
        return "Node_" + key + "_" + value;
    }
}
复制代码

2、clean实现

遍历数组，清空数组的每一个节点。

@Override
public void clear() {
    if (size == 0) return;
    size = 0;
    for (int i = 0; i < table.length; i++) {
        table[i] = null;
    }
}
复制代码

3、put实现

在进行插入操作时，通过比较key和key.parent的哈希值大小，来决定插入位置。
如果哈希值相同，则比较equals。
如果equals相同，则比较类名。
如果类名相同（同一种类型），则查看是否实现comparable，如果实现，则直接通过该函数比较。
如果相同类型，不具有可比较性，或其中一个数据为空，则比较内存地址。
直接比较内存地址会导致结果不稳定，应该先扫码树中是否有该值，如果没有，再比较内存地址。

@Override
public V put(K key, V value) {
    resize();

    int index = index(key); // 获取key对应的索引
    Node<K, V> root = table[index]; // 取出index位置的红黑树根节点
    if (root == null) { // 如果根节点为空
        root = createNode(key, value, null);
        table[index] = root;
        size++;
        fixAfterPut(root);
        return null;
    }

    //  如果根节点不为空，添加新的节点到红黑树上面
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    K k1 = key;
    int h1 = hash(k1);
    Node<K, V> result = null;
    boolean searched = false; // 是否已经搜索过这个key
    do {
        parent = node;
        K k2 = node.key;
        int h2 = node.hash;
        // 根据哈希值来进行比较，大的放右边，小的放左边。
        if (h1 > h2) {
            cmp = 1;
        } else if (h1 < h2) {
            cmp = -1;
        } else if (Objects.equals(k1, k2)) {
            cmp = 0;
        } else if (k1 != null && k2 != null 
            && k1 instanceof Comparable
            && k1.getClass() == k2.getClass()
            && (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
        } else if (searched) { // 已经扫描了
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
        } else { // searched == false; 还没有扫描，然后再根据内存地址大小决定左右
        if ((node.left != null && (result = node(node.left, k1)) != null)
        || (node.right != null && (result = node(node.right, k1)) != null)) {
            // 已经存在这个key
            node = result;
            cmp = 0;
        } else { // 不存在这个key
            searched = true;
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2); //根据内存地址计算出的hashcode
        }
    }

    if (cmp > 0) { // 大于
        node = node.right;
    } else if (cmp < 0) { //小于
        node = node.left;
    } else { // 相等
        V oldValue = node.value;
        node.key = key;
        node.value = value;
        node.hash = h1;
        return oldValue;
    }
} while (node != null);

// 看看插入到父节点的哪个位置
Node<K, V> newNode = createNode(key, value, parent);
if (cmp > 0) {
    parent.right = newNode;
} else {
    parent.left = newNode;
}
size++;

// 新添加节点之后的处理
fixAfterPut(newNode);
return null;
}

/**
* 根据key生成对应的索引（在桶数组中的位置）
*/
private int index(K key) {
    return hash(key) & (table.length - 1); //先求哈希值，再做位运算
}

private int hash(K key) {
    if (key == null) return 0;
    int hash = key.hashCode();
    return hash ^ (hash >>> 16); //高16位与低16位做一次运算
}
复制代码

3、get实现

首先确定key的索，然后再寻找索引下的树。

@Override
public V get(K key) {
    Node<K, V> node = node(key);
    return node != null ? node.value : null;
}

private Node<K, V> node(K key) {
    //根据key生成对应的索引
    //根据索引在数组中找到根节点。
    Node<K, V> root = table[index(key)];
    return root == null ? null : node(root, key); 
}

private Node<K, V> node(Node<K, V> node, K k1) {
    int h1 = hash(k1);
    // 存储查找结果
    Node<K, V> result = null;
    int cmp = 0;
    while (node != null) {
        K k2 = node.key;
        int h2 = node.hash;
        // 先比较哈希值
        if (h1 > h2) {
            node = node.right;
        } else if (h1 < h2) {
            node = node.left;
        } else if (Objects.equals(k1, k2)) { //可比较性
            return node;
        } else if (k1 != null && k2 != null 
                && k1 instanceof Comparable
                && k1.getClass() == k2.getClass()
                && (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
                node = cmp > 0 ? node.right : node.left;
        } 
        // 走到这里，表示哈希值相等，不具备可比较性，也不 equals
        else if (node.right != null && (result = node(node.right, k1)) != null) { //先找右子树
            return result;
        } else { // 再去左边扫码
            node = node.left;
        }
    }
    return null;
}
复制代码

4、remove实现

@Override
public V remove(K key) {
    return remove(node(key));
}

protected V remove(Node<K, V> node) {
    if (node == null) return null;

    Node<K, V> willNode = node;

    size--;

    V oldValue = node.value;

    if (node.hasTwoChildren()) { // 度为2的节点
        // 找到后继节点
        Node<K, V> s = successor(node);
        // 用后继节点的值覆盖度为2的节点的值
        node.key = s.key;
        node.value = s.value;
        node.hash = s.hash;
        // 删除后继节点
        node = s;
    }

    // 删除node节点（node的度必然是1或者0）
    Node<K, V> replacement = node.left != null ? node.left : node.right;
    int index = index(node);

    if (replacement != null) { // node是度为1的节点
        // 更改parent
        replacement.parent = node.parent;
        // 更改parent的left、right的指向
        if (node.parent == null) { // node是度为1的节点并且是根节点
            table[index] = replacement;
        } else if (node == node.parent.left) {
            node.parent.left = replacement;
        } else { // node == node.parent.right
            node.parent.right = replacement;
        }
        // 删除节点之后的处理
        fixAfterRemove(replacement);
    } else if (node.parent == null) { // node是叶子节点并且是根节点
        table[index] = null;
    } else { // node是叶子节点，但不是根节点
        if (node == node.parent.left) {
            node.parent.left = null;
        } else { // node == node.parent.right
            node.parent.right = null;
        }
        // 删除节点之后的处理
        fixAfterRemove(node);
    }

    // 交给子类去处理
    afterRemove(willNode, node);
    return oldValue;
}
复制代码

5、containsValue实现

检测哈希表中是否存在某值，只有遍历每一个树，使用层序遍历实现。

@Override
public boolean containsValue(V value) {
    if (size == 0) return false;
    Queue<Node<K, V>> queue = new LinkedList<>();
    for (int i = 0; i < table.length; i++) {
        if (table[i] == null) continue;

        queue.offer(table[I]);
        while (!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            if (Objects.equals(value, node.value)) return true;

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    return false;
}
复制代码

6、扩容

当哈希表的table数组中添加元素过多后，哈希冲突概率增大，效率变低。所以要根据装填因子判断是否需要扩容。
装填因子：节点总数量 / 哈希表桶数组长度，也叫做负载因子。
在JDK1.8的HashMap中，如果装填因子超过0.75，就扩容为原来的2倍。
如果装填因子超过0.75，就将数组长度扩大为原来的两倍，并将原来的数据迁移进新数组。
扩容之后，原来数据算出的节点值就有可能不一样了（保持不变或index = index + 旧容量），因为节点的计算需要涉及到table.length。

private void resize() {
    // 装填因子 <= 0.75
    if (size / table.length <= DEFAULT_LOAD_FACTOR) return;

    Node<K, V>[] oldTable = table;//保留旧的数组
    table = new Node[oldTable.length << 1];//将数组长度变为原来的2倍

    //层序遍历
    Queue<Node<K, V>> queue = new LinkedList<>();
    for (int i = 0; i < oldTable.length; i++) {
        if (oldTable[i] == null) continue;

        queue.offer(oldTable[I]);
        while (!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }

            // 挪动代码得放到最后面
            moveNode(node);
        }
    }
}

private void moveNode(Node<K, V> newNode) {
    // 重置节点属性
    newNode.parent = null;
    newNode.left = null;
    newNode.right = null;
    newNode.color = RED;

    int index = index(newNode);
    // 取出index位置的红黑树根节点
    Node<K, V> root = table[index];
    if (root == null) {
        root = newNode;
        table[index] = root;
        fixAfterPut(root);
        return;
    }

    // 添加新的节点到红黑树上面
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    K k1 = newNode.key;
    int h1 = newNode.hash;
    do {
        parent = node;
        K k2 = node.key;
        int h2 = node.hash;
        if (h1 > h2) {
            cmp = 1;
        } else if (h1 < h2) {
            cmp = -1; // 不用再比较equals，因为不会存在重复数据。
        } else if (k1 != null && k2 != null 
                && k1 instanceof Comparable
                && k1.getClass() == k2.getClass()
                && (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
        } else { // 搜索也不需要，原因同上。
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
        }

        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        }
    } while (node != null);

    // 看看插入到父节点的哪个位置
    newNode.parent = parent;
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }

    // 新添加节点之后的处理
    fixAfterPut(newNode);
}
复制代码

7、equals的优化

我们在添加元素时，要谨防因equals的函数实现有问题，导致a.equals(b)和b.equals(a)的结果不一致。
所以在实现equals函数时，要遵循以下条件：

image

四、TreeMap VS HashMap

TreeMap增删改查都是O(logn)级别，而哈希表是O(1)级别。
当元素具备可比较性且要求升序遍历时，使用TreeMap。当对遍历没有要求时，选择HashMap。

五、LinkedHashMap

在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵循添加顺序的。
假设添加顺序是37，21，31，41，97，95，52，42，83

image

六、LinkedHashMap的接口实现

新增first和last两个属性。

public class LinkedHashMap<K, V> extends HashMap<K, V> {
    private LinkedNode<K, V> first;
    private LinkedNode<K, V> last;
}
复制代码

给Node增加前驱和后继两个指针。

private static class LinkedNode<K, V> extends Node<K, V> {
    LinkedNode<K, V> prev;
    LinkedNode<K, V> next;
    public LinkedNode(K key, V value, Node<K, V> parent) {
        super(key, value, parent);
    }
}
复制代码

添加一个构造节点的函数。

@Override
protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
    LinkedNode node = new LinkedNode(key, value, parent);
    if (first == null) { //没有头节点
        first = last = node;
    } else { //有头节点
        last.next = node;
        node.prev = last;
        last = node;
    }
    return node;
}
复制代码

clear函数需要清空first和last指针。

@Override
public void clear() {
    super.clear();
    first = null;
    last = null;
}
复制代码

遍历函数

@Override
public void traversal(Visitor<K, V> visitor) {
    if (visitor == null) return;
    LinkedNode<K, V> node = first;
    while (node != null) {
        if (visitor.visit(node.key, node.value)) return;
        node = node.next;
    }
}
复制代码

删除函数，不仅仅需要删除数据，还需要修改指针指向。
删除度为2的节点时，需要注意更换node与前驱/后继节点的链接位置。
例如，删除31

image

@Override
protected void afterRemove(Node<K, V> willNode, Node<K, V> removedNode) {
    LinkedNode<K, V> node1 = (LinkedNode<K, V>) willNode;
    LinkedNode<K, V> node2 = (LinkedNode<K, V>) removedNode;

    if (node1 != node2) {
        // 交换linkedWillNode和linkedRemovedNode在链表中的位置
        // 交换prev
        LinkedNode<K, V> tmp = node1.prev;
        node1.prev = node2.prev;
        node2.prev = tmp;
        if (node1.prev == null) {
            first = node1;
        } else {
            node1.prev.next = node1;
        }
        if (node2.prev == null) {
            first = node2;
        } else {
            node2.prev.next = node2;
        }

        // 交换next
        tmp = node1.next;
        node1.next = node2.next;
        node2.next = tmp;
        if (node1.next == null) {
            last = node1;
        } else {
            node1.next.prev = node1;
        }
        if (node2.next == null) {
            last = node2;
        } else {
            node2.next.prev = node2;
        }
    }

    LinkedNode<K, V> prev = node2.prev;
    LinkedNode<K, V> next = node2.next;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
    }
}
复制代码

核心就是交换。

image

遍历节点

@Override
public boolean containsValue(V value) {
    LinkedNode<K, V> node = first;
    while (node != null) {
        if (Objects.equals(value, node.value)) return true;
        node = node.next;
    }
    return false;
}
复制代码

数据结构与算法（第一季）：哈希表（Hash Table）

一、哈希表（Hash Table）

1、概念

2、哈希冲突

3、JDK1.8的哈希冲突解决方案

4、哈希函数

5、如何生成hash_code(key)

5.1、整数的哈希值

5.2、浮点数的哈希值

5.2、`Long`和`Double`的哈希值

5.3、字符串的哈希值

5.4、自定义对象的哈希值

5.5、自定义对象存储举例

二、哈希表的接口设计（HashMap）

三、哈希表的实现（HashMap）

1、声明节点

2、clean实现

3、put实现

3、get实现

4、remove实现

5、containsValue实现

6、扩容

7、equals的优化

四、TreeMap VS HashMap

五、LinkedHashMap

六、LinkedHashMap的接口实现

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构与算法（第一季）：哈希表（Hash Table）

一、哈希表（Hash Table）

1、概念

2、哈希冲突

3、JDK1.8的哈希冲突解决方案

4、哈希函数

5、如何生成hash_code(key)

5.1、整数的哈希值

5.2、浮点数的哈希值

5.2、Long和Double的哈希值

5.3、字符串的哈希值

5.4、自定义对象的哈希值

5.5、自定义对象存储举例

二、哈希表的接口设计（HashMap）

三、哈希表的实现（HashMap）

1、声明节点

2、clean实现

3、put实现

3、get实现

4、remove实现

5、containsValue实现

6、扩容

7、equals的优化

四、TreeMap VS HashMap

五、LinkedHashMap

六、LinkedHashMap的接口实现

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

5.2、`Long`和`Double`的哈希值