JAVA数据结构 & 哈希表 -HashSet and HashMap

引例

在讲这个部分之前，请试着去做一下下面这道题。

题：给定一串序列（char[] (小写字母)），要求你将其排序并且不能出现重复也不能有一个缺席。

没错，我们可以这么做：

char[] arr = new char[26];
//假设ch 为某个小写字母;
arr[ch - 'a']++;

我们可以讲这个字母减掉’ ‘ a ’（即 97），这样a对应0，b对应1…

这样我们就只需要遍历一遍数组，只要不是’\u0000’(默认值),就打印or其他。

并且也可以快速知道对应字母的个数。

这样的思想就是“哈希思想”，把一个元素以特定的方法放进数组里，只要知道这个方法，就可以快速查找并且快速发现重复…

Set和Map的最大用处就是查找！

哈希的时间复杂度甚至达到了O(1)！

因为根据下标来找，太快了！

1. 哈希方法导致的冲突

细心的同学可能发现了，用同一个哈希方法的话，避免不了两个元素放在了同一个位置去了，那么我们就需要避免和解决。

1.1 冲突的避免（从整体减少冲突的次数）

这里要用到一个负载因子常量的概念（其他地方可能有其他的说法）

这个负载因子就是哈希表中【已经放入的元素的个数 / 表最大容量】的最大值

一些实验数据事实表明：

哈希表越满越容易冲突

呈现出S型趋势

设计：

只需要让实际的负载因子时刻小于这个最大值，一旦大于等于这个最大值的时候，就让数组扩容。

也面临了另一个大问题，就是扩容后，需要重新将每个元素按照原本的哈希方法放进哈希表。

public static final double Load_FACTOR = 0.75;//一直处于七五分满

1.2 冲突的解决

1.2.1 闭散列

散列这个说法一些书籍仍在使用【哈希表的意思】

那么闭散列就是在顺序表内部解决这个问题

至于用顺序表是因为下标访问快

线性探测法

发现用哈希方法解析后的下标，已经被占用，那么从左往右探测，第一个空的就可以放上去

缺点很大：放的效率很低，取的时候效率也低，要找的那个位置不是我们要的数据，那么就要“线性探测”从左往右遍历找我们的数据。

并且我们很难去区分这个位置是否有元素，比如int[] 可能值就是0，引用类型也可能值就是null，怎么就能说明那个位置空了呢？

很容易达到负载值而需要重新扩容

这个方法很少用，最多出道题恶心人。

例如问，按照线性探测法找，需要多少步？

二次探测法

本质上跟【线性探测法】的思路是一致的，放在顺序表的其他空的位置。

但是这个方法是按照一个规律去实现的

Hi = (H0 + i2) % m【m为表的大小，H代表哈希值(后面会讲)】

Hi = (H0 - i2) % m【或者是这种】

【i】就是“跳跃的次数”，即第一次发现该位置有人，跳一次，此时 i为1

跳一次后发现位置还是有元素，再次跳一次，此时 i为2

注意：放置的时候发现没有元素，即 i为0

如下图所示（e代表元素element）：

这种方法是线性探测法的优化，加快了放置查找的速度

其他缺点依旧一个不落的继承

1.2.2 开散列（哈希桶）

也就是在顺序表“外”

如图所示，让数组的类型为“链表的节点”，遇到该位置已经被占用，就头插进去就好

用带头+尾插的技巧也是完全可以的，因为插入的时候都是要检测是否重复的，自然到达链尾很容易

有些地方用二叉搜索树，甚至高度平衡的二叉树【即红黑树】

如下图所示：

是否是就很像一个一个的“桶”

所以才叫哈希桶

2. 基础简单的HashSet的模拟

用简单的 int(基本数据类型)

如下图的大概模板

属性：

节点数组

已存放元素个数

负载因子最大值

方法：

构造方法

放置方法（重复则覆盖）

扩容重塑方法

计算负载因子方法

获取key键方法（这里可以认为是判断是否存在）

这里如果是Map，则对应返回的应该是键值对key对应的value值

public class HashBuck {//哈希桶法
    static class Node {
    }
    public Node[] array;
    public int useSize;
    public static final double Load_FACTOR = 0.75;//"全局"常数
    public HashBuck() {
        array = new  Node[10];
    }
    public void put(int key) {
    }
    private void resize() {
    }
    private double calculateLoadFactor() {
    }
    public boolean get(int key) {
    }
}

2.1 属性

2.1.1 节点

//静态内部类
static class Node {
    public int key;
    public Node next;
    public Node(int key) {
        this.key = key;
    }
}
public Node[] array;

2.1.2 已存放元素个数以及实际负载因子

public int useSize;
public static final double Load_FACTOR = 0.75;//"全局"常数

2.2 方法

2.2.1 构造方法

public HashBuck() {
    array = new  Node[10];//默认大小为10
}

2.2.2 放置方法

哈希方法我并没有直接做一个方法出来，一般就是一条表达式而已

这里是 int index = key % array.length;【取模法是很常见的】

public void put(int key) {
    int index = key % array.length;
    Node cur = array[index];
    //检测
    while(cur != null) {
        if(cur.key == key) {
            return;
        }else {
            cur = cur.next;
        }
    }
    //头插
    Node newOne = new Node(key);
    newOne.next = array[index];
    array[index] = newOne;
    //已存放元素+1，并且计算是否超过负载因子最大值，若超过，则扩容重塑
    useSize++;
    if(calculateLoadFactor() > Load_FACTOR) {
        resize();
    }
}

2.2.3 计算负载因子方法

private double calculateLoadFactor() {
    return (double) useSize / array.length;
}

2.2.4 扩容重塑方法

只需要遍历节点数组【哈希表】，null一定代表没有数据

不是null的就将该链表遍历一遍，每一个键值重新放置

这里拿一个新的数组放的原因是，重新放置可能会放在前面也可能放置到后面，那么这个值等一下可能又会被遍历到。

private void resize() {
        //扩容两倍，当然可以其他倍数（系统为1.5倍，随后细说）
        Node[] newArr = new Node[array.length * 2];
        //重塑
        for (int i = 0; i < array.length; i++) {
            while(array[i] != null) {
                int index = array[i].key % newArr.length;
                Node cur = newArr[index];
                Node newOne = new Node(array[i].key);
                if(cur == null) {
                    newArr[index] = newOne;
                }else {
//  尾插法              while(cur.next != null) {
//                        cur = cur.next;
//                    }
//                    cur.next = new Node(array[i].key, array[i].val);
                    newOne.next = cur;
                    newArr[index] = newOne;
                }
                array[i] = array[i].next;
            }
        }
        //指向新的节点数组
        array = newArr;

2.2.5 获取key键方法

public boolean get(int key) {
    int index = key % array.length;
    Node cur = array[index];
    while(cur != null) {
        if(cur.key == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

我在这里就不测试了

3. HashMap的模拟

在【2】的基础下，只需要让节点多一个成员，则多出一层“映射关系”，这就是Map映射

如下代码，大致与上面相似

key为自变量，不能重复，重复则覆盖（value值更改）

public class HashBuck {
    static class Node {
        public int key;
        public int val;
        public Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;
    public int useSize;
    public static final double Load_FACTOR = 0.75;//"全局"常数

public HashBuck() {
        array = new  Node[10];
    }
    public void put(int key, int val) {
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if(cur.key == key) {
                cur.val = val;
                return;
            }else {
                cur = cur.next;
            }
        }
        Node newOne = new Node(key, val);
        newOne.next = array[index];
        array[index] = newOne;
        useSize++;
        if(calculateLoadFactor() > Load_FACTOR) {
            resize();
        }
    }
    private void resize() {
        Node[] newArr = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            while(array[i] != null) {
                int index = array[i].key % newArr.length;
                Node cur = newArr[index];
                Node newOne = new Node(array[i].key, array[i].val);
                if(cur == null) {
                    newArr[index] = newOne;
                }else {
//  尾插               while(cur.next != null) {
//                        cur = cur.next;
//                    }
//                    cur.next = new Node(array[i].key, array[i].val);
                    newOne.next = cur;
                    newArr[index] = newOne;
                }
                array[i] = array[i].next;
            }
        }
        array = newArr;
    }
    private double calculateLoadFactor() {
        return (double) useSize / array.length;
    }
    public int get(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
}

4. 数据类型为引用类型

我们刚才用的是int[ ] ，如果是String类型，自定义类型呢？

那么这里就需要用到一个方法hashcode() ，这个方法可以获取到哈希值（引用类型的身份证），这样就可以进行取模运算了

如果是自定义类型，我们得自己重写hashcode()方法,String系统已经重写了

一定一定要重写equals()方法，否则我们认为相同的两个引用，哈希值也会不同

下面是泛型版本：

public class MyHashMap <K, V> {
    //如果用到泛型的话，记住要重写一些方法，如equals 和 hashCode
    //以及在特定位置补上自己的哈希方法
    static class Node<K, V> {
        public K key;
        public V val;
        public Node<K, V> next;
        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node<K, V>[] array;
    public int useSize;
    public static final double Load_FACTOR = 0.75;//"全局"常数
    public MyHashMap() {
        array = (Node<K,V>[])(new Node[10]);
    }
    public void put(K key, V val) {
        int index = key.hashCode() % array.length;
        Node<K, V> cur = array[index];
        while(cur != null) {
            if(cur.key.equals(key)) {
                cur.val = val;
                return;
            }else {
                cur = cur.next;
            }
        }
        Node<K, V> newOne = new Node<>(key, val);
        newOne.next = array[index];
        array[index] = newOne;
        useSize++;
        if(calculateLoadFactor() > Load_FACTOR) {
            resize();
        }
    }
    private void resize() {
        Node<K, V>[] newArr = (Node<K,V>[]) (new Node[array.length * 2]);
        for (int i = 0; i < array.length; i++) {
            while(array[i] != null) {
                int index = array[i].key.hashCode() % newArr.length;
                Node<K, V> cur = newArr[index];
                Node<K, V> newOne = new Node<>(array[i].key, array[i].val);
                if(cur == null) {
                    newArr[index] = newOne;
                }else {
//  尾插               while(cur.next != null) {
//                        cur = cur.next;
//                    }
//                    cur.next = new Node(array[i].key, array[i].val);
                    newOne.next = cur;
                    newArr[index] = newOne;
                }
                array[i] = array[i].next;
            }
        }
        array = newArr;
    }
    private double calculateLoadFactor() {
        return (double) useSize / array.length;
    }
    public V get(int key) {
        int index = key % array.length;
        Node<K, V> cur = array[index];
        while(cur != null) {
            if(cur.key.equals(key)) {
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}

数组的构建参考的是hashMap源码

下面是随便一个自定义类：

class student {
    char[] name;
    int id;
    int score;
}

【Alt + insert】后点击这个东西,一路next就好了

我们也可以自己去决定“怎么样才算相等”，自己重写equals（）

【JAVA数据结构】哈希表-HashSet and HashMap