哈希

谈论哈希之前，我们先来谈谈数组。在之前的一些线性结构中，其实数组中的某个元素的索引这个信息并没有好好的利用到。

对于一个char数组，我把a这个字符放在数组的第一个位置或者数组的最后一个没什么区别。

诚然，很多时候我们关注数组的有序性，但这个其实是关注数组中元素的相对位置，而不是它们的索引。我们根本就不在乎一个元素的索引是1，还是10。

从信息论的角度来说，我们浪费了这个信息。

而hash的思想在于：对于任意一个对象（或者说元素、个体。。。），我们都可以按照一定的规则把它映射为一个数字。然后我们就可以把这个数字和数组的索引结合起来。

上面说的一定的规则中的规则可以有很多种，举个例子：

对于一个整数a,我们可以按照下面的规则来转化

function hash(a){
  return a % 7;
}

如果是按照上面的映射关系的话：

7 ---> 0
8 ---> 1
16 --> 2
。。。

那这样的好处是什么？

对于任意的整数，我们都可以把它hash成[0,7)之间的整数。

除了可以对整数hash，其实任何数据都可以对它hash，得到一个整数的结果。

比如Hello,woeld这个字符串，如果我们认为哈希函数是

function hash(str){
  return str.length
}

那么它的hash结果就是11。不过这个哈希函数写的很差，任意长度为11的字符串的hash结果都是11，非常容易冲突。

更好的写法可以参考java.lang.String.hashCode的实现，我这里不多说了。

现在我们可以自己来实现一个HashSet。思路就是维护一个数组，每当我们想向集合中添加一个元素的时候，我们先计算这个元素的hash值，如果hash值是k，我们就把这个元素放在数组索引为k的位置。

考虑到不同的元素可能有相同的hash值，我们认为数组的每个位置都是一个容器（比如说链表）。然后把元素放到链表中，以后即使hash冲突了，也没有关系。

下面是代码的基本骨架

/**
 * 其实是一个有序集合，可以轻易的从小到大的遍历
 * @param <E>
 */
@ToString
public class HashSet<E> {
    private List<E>[] hashSet;

    /**
     * Hash数组的长度
     */
    private int M;

    public HashSet(int M){
        this.M = M;
        hashSet = new List[M];
        for (int i = 0; i < M; i++) {
            hashSet[i] = new LinkedList<>();
        }
    }
    public HashSet(){
        this(97);
    }

    private int hash(E e){
        return (e.hashCode() & 0x7fffffff) % M;
    }
}

我们的内部维护了一个数组，数组中的每个元素都是一个链表。

我们要是想添加元素可以怎么做？我们直接把e添加到数组中索引为hash(e)的链表中就行了。

具体代码就是这样的

    public void add(E e) {
        hashSet[hash(e)].add(e);
    }

同理，我们可以写出查询和删除

    public void remove(E e) {
        hashSet[hash(e)].remove(e);
    }

    public boolean contains(E e) {
        return hashSet[hash(e)].contains(e);
    }

下面是完整的代码。

import lombok.ToString;

import java.util.LinkedList;
import java.util.List;

@ToString
public class HashSet<E> {
    private List<E>[] hashSet;

    /**
     * Hash数组的长度
     */
    private int M;

    public HashSet(int M){
        this.M = M;
        hashSet = new List[M];
        for (int i = 0; i < M; i++) {
            hashSet[i] = new LinkedList<>();
        }
    }
    public HashSet(){
        this(97);
    }

    private int hash(E e){
        return (e.hashCode() & 0x7fffffff) % M;
    }

    public void add(E e) {
        hashSet[hash(e)].add(e);
    }

    public void remove(E e) {
        hashSet[hash(e)].remove(e);
    }

    public boolean contains(E e) {
        return hashSet[hash(e)].contains(e);
    }
}

fish-stack / Algo

哈希 #6

哈希