[数据结构与算法]能带你起飞的【数据结构】成王第十七篇:哈希表 1

前言

?

内部类

1.本地内部类:定义在方法当中的内部类

用的非常的少,而且轻易不要去写一些本地内部类

2.实例内部类:定义在类内部方法的外部叫做实例内部类

?①:在实例内部类当中,不能定义一个静态的成员变量

?如果非要定义,只能定义1个,静态常量

?也可以写构造方法

实例化内部类对象

?如何继承内部类

?

实例内部类当中,如果包含了和外部类同名的成员变量,那么如何在实例内部类当中访问

?实例内部类当中包含两个this.一个是外部类的this,一个是自己的this

3.静态内部类

?

4.匿名内部类

?

??

哈希表

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键 码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( )，搜索的效率取决于搜索过程中 元素的比较次数。?

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函 数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快 找到该元素。?

?在我们存放的数据的时候就知道存在这个位置,取的时候也直接从这个位置取出来,这样的话时间复杂度就可以达到O(1),一下就能拿到想拿的元素说明知道怎样拿到,可以通过某种办法拿到.这就是我们的哈希表->HashMap

如果要放一个元素x到表里,通过一个函数,让这个x通过函数的操作放在某个位置了,然后当我们要取取x的时候,就可以通过这个函数取出来,这函数我们就叫做哈希函数

假设我们有一个数组,有一些数字,我们要把这些数字都放到数组里面,怎么来放呢,我们要通过哈希函数来放,这个哈希函数是可以自己来设计的

?现在我们假设要放1,通过哈希函数,key取模一个容量,key是1,容量是10,? ?1%10余1

所以1就放到1下标的位置

取也通过这个哈希函数,怎么存的怎么取

但是在这当中会发生一些问题,假设要存14进去.? 14 % 10 结果也是4.但是此时4下标已经有数据了. 所以说不同的关键字通过相同的哈希函数,有可能找到相同的位置.此时的情况:哈希冲突/哈希碰撞

冲突:不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞

既然发生冲突了,那么可不可以在发生冲突之前进行避免

首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一 个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 哈希函数设计原则： 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1 之间 哈希函数计算出来的地址能均匀分布在整个空间中

常见哈希函数

1. 直接定制法--(常用) 取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关 键字的分布情况 使用场景：适合查找比较小且连续的情况?

2. 除留余数法--(常用) 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数： Hash(key) = key% p(p<=m),将关键码转换成哈希地址

冲突-避免-负载因子调节?

负载因子 = 存储散列表的元素的个数/散列表的长度

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。 已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。

解决冲突

?1.闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

以下表举例

比如说要存放44,通过哈希函数找到4下标位置,发现4下表位置有数据,此时怎么去做呢,线性探测,从4下标位置开始,向后找到第一个为空的位置,放44

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

比如再放14,24,34

缺点:会把冲突的元素都放到一起了?

如果要删除的元素的时候,不能直接把4删掉,找44,找44就需要找到4下标,发现4下标没有元素,那后面的元素就找不到了,所以线性探测删除元素就比较麻烦.所以需要在4下标这个地方加一个标志位,假设没删掉的时候是0,删除了是1

2.2次探测

假设从头开始继续放44,就是放在4*1的平方,放在5下标位置

当再放14的时候是第二次冲突就放在4*2的平方等于8,就把14放在了8下标位置

24是第三次冲突,就是4+9 = 13 % 10 ,放到3下标

当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不 会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情 况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。?

2.冲突-解决-开散列/哈希桶（重点掌握）?

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子 集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

什么叫做开散列

每个数组是一个桶,桶里面放的是一个节点,节点有三个域key、value、next

假设放4这个值,4对应的value假设是一个字符串,然后就把这个节点通过哈希函数放到4下标位置

现在数组是一个Node[]的数组

?此时比如要放一个14,14通过哈希函数也要放到4下标位置,通过尾插法

?

?这样的话所有冲突的元素都挂到了这个链表上

这种解决方案就叫做哈希桶

因为有负载因子的存在,所以链表的长度不会很长,控制在常数范围内

JDK1.8开始,当链表的长度超过8,这个链表就会编程红黑树,但是:数组的长度要超过64

虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的， 也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 。?

实现哈希桶代码

整数类型的哈希桶

class Node1{
    public int key;
    public int val;
    public Node1 next;

    public Node1(int key, int val) {
        this.key = key;
        this.val = val;
    }
}
public class HashBuck {

    public Node1[] array;
    public int usedsize;

    public static final double DEFAULT_LOADFACTOR = 0.75;

    public HashBuck() {
        this.array = new Node1[10];

    }


    /**
     * put函数
     *
     * @param key
     * @param val
     */
    public void put(int key, int val) {
        //1.找到key所在的位置
        int index = key % array.length;

        //2.遍历这个下标的链表,看看是不是有相同的key.有,要更新val值
        Node1 cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;//更新val值
                return;
            }
            cur = cur.next;
        }
        //3.如果没有key这个元素,头插法
        Node1 node1 = new Node1(key, val);
        node1.next = array[index];
        array[index] = node1;
        this.usedsize++;
        //4.插入元素成功之后,检查当前散列表的负载因子
        if (loadFactor() > DEFAULT_LOADFACTOR) {

        }


    }

    //如果扩容数组那么数组里面的每个链表的的每个元素都要进行重新哈希
    private void resize() {
        Node1[] newArray = new Node1[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node1 cur = array[i];
            while (cur != null) {
                int index = cur.key % newArray.length;//获取新的下标
                //就是把cur这个节点,以头插或者尾插的形式 插入到新的数组对应的下标的链表当中
                Node1 curNext = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }

        }
        array = newArray;
    }

    private double loadFactor() {

        return 1.0 * usedsize / array.length;
    }

    /**
     * 根据key获取val值
     *
     * @param key
     * @return
     */
    public int get(int key) {
        //1.找到key所在的位置
        int index = key % array.length;
        //2.遍历这个下标的链表,看看是不是有相同的key.有,要更新val值
        Node1 cur = array[index];
        while (cur != null) {
            if (cur.key == key) {

                return cur.val;
            }
            cur = cur.next;
        }
        return -1;

    }

    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.put(1,1);
        hashBuck.put(11,11);
        hashBuck.put(2,2);
        hashBuck.put(12,12);
        hashBuck.put(3,3);
        hashBuck.put(6,6);
        System.out.println(hashBuck.get(3));



    }
}

hashcode

这个函数能够解决如果是引用类型情况下,不是整数,把它变成合法的整数

定义一个person类

class Person{
    public String ID;

    public Person(String ID) {
        this.ID = ID;
    }

    @Override
    public String toString() {
        return "Person{" +
                "ID='" + ID + '\'' +
                '}';
    }
}
public class HashBuck2 {
    public static void main(String[] args) {
        Person person1 = new Person("123");
        Person person2 = new Person("123");
    }
}

假设key是一个person

?hashcode确定位置 equals来观察key的值一不一样,一样的话替换val

hashcode一样只能证明位置下标是一样的

hashcode的一样,equals不一定一样

equals一样了hashcode一定是一样的

class Person{
    public String ID;

    public Person(String ID) {
        this.ID = ID;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(ID, person.ID);
    }

    @Override
    public int hashCode() {
        return Objects.hash(ID);
    }

    @Override
    public String toString() {
        return "Person{" +
                "ID='" + ID + '\'' +
                '}';
    }
}
class Node3<K,V> {
    public K key;
    public V val;
    public Node3<K, V> next;

    public Node3(K key, V val) {
        this.key = key;
        this.val = val;
    }


}
public class HashBuck2<K,V>{
    public Node3<K,V>[] array = (Node3<K,V>[])new Node3 [10];
    public int usedsize;

    public static final double DEFAULT_LOADFACTOR = 0.75;

    public void put( K key,V val){
        int index = key.hashCode() % array.length;
        Node3<K,V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                cur.val = val;//更新val值
                return;
            }
            cur = cur.next;
        }
        //3.如果没有key这个元素,头插法
        Node3<K,V> node3 = new Node3<>(key, val);
        node3.next = array[index];
        array[index] = node3;
        this.usedsize++;
        //4.插入元素成功之后,检查当前散列表的负载因子
        if (loadFactor() > DEFAULT_LOADFACTOR) {

        }

    }
    //如果扩容数组那么数组里面的每个链表的的每个元素都要进行重新哈希
    private void resize() {
        Node3<K,V>[] newArray = ( Node3<K,V>[])new Node3[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node3<K,V> cur = array[i];
            while (cur != null) {
                int index = cur.key.hashCode() % newArray.length;//获取新的下标
                //就是把cur这个节点,以头插或者尾插的形式 插入到新的数组对应的下标的链表当中
                Node3<K,V> curNext = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }

        }
        array = newArray;
    }

    private double loadFactor() {

        return 1.0 * usedsize / array.length;
    }

    public V get(K key){
        //1.找到key所在的位置
        int index = key.hashCode() % array.length;
        //2.遍历这个下标的链表,看看是不是有相同的key.有,要更新val值
        Node3<K,V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)){

                return cur.val;
            }
        }
        return null;


    }

    public static void main(String[] args) {
        Person person1 = new Person("123");
        Person person2 = new Person("123");

        HashBuck2<Person,String> hashBuck2 = new HashBuck2<>();
        hashBuck2.put(person1,"bit");
        System.out.println(hashBuck2.get(person2));

        System.out.println(person1.hashCode());
        System.out.println(person2.hashCode());
    }


}

?

?