HashSet和HashMap以及Hash相关知识点

Hash的概念

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值,简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

Hash冲突　(4种解决方案)

1、开放寻址法 2、链地址法 3、再哈希 4、建立一个公共溢出区

HashSet：

将对象存储在HashSet之前，要确保重写hashCode（）方法和equals（）方法，这样才能比较对象的值是否相等，确保集合中没有储存相同的对象。

HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashSet实战
加入的对象需要重写equals和hashcode方法

//重写了,因此修改了对象的熟性 会改变Hashcode的值
//往hashset插入时，存储进去的是以第一次放入的hashcode为主，后面即使改了对象的属性，仍然存储的是第一次的hashcode
//对象放进来时 先判断hashcode是否相等，相等在判断属性值是否相等

下面是神奇的代码时刻

package com.scma.Hash;

import java.util.HashSet;

public class TestHashSet {
    public static void main(String[] args) {
        HashSet<Person> set = new HashSet<Person>();
        Person p1 = new Person("AA",1001);
        Person p2 = new Person("BB",1002);

        set.add(p1);
        set.add(p2);
        System.out.println("1:" +set);
        System.out.println("p1的Hash值:" +p1.hashCode());
        p1.setName("CC");
        System.out.println("p1的Hash值(修改后):" +p1.hashCode());
        set.remove(p1);// 此时p1对象已经被修改了，remove()是根据修改后的对象的hash值，找对应的位置，因此此时删除时对应的位置没有值，所以此时没有删除出任何数据。
        System.out.println("2:" +set);

        Person p3 = new Person("CC", 1001); //虽然此对象与p1对象值完全相等，但是添加时，添加到了该对象所对应的hash桶，而此时的位置与p1不是同一个位置，因为p1是根据修改之前的hash值放入对应的has桶内的，因此他们不冲突
        set.add(p3);
        System.out.println("3:" +set);
        
        set.add(new Person("AA",1001));// 值与未修改前的p1值完全相等，所以对应的hash桶也是同一个位置，添加时找到对应的桶位置后，发现已经有一个对象，然后用equals方法比较值，此时值不相等，因此不产生冲突，依然可以加入到HashSet中
        System.out.println("4:" +set);
    }
}

输出结果：

1:[Person [name=AA, id=1001], Person [name=BB, id=1002]]
p1的Hash值:62390
p1的Hash值(修改后):62454
2:[Person [name=CC, id=1001], Person [name=BB, id=1002]]
3:[Person [name=CC, id=1001], Person [name=CC, id=1001], Person [name=BB, id=1002]]
4:[Person [name=CC, id=1001], Person [name=CC, id=1001], Person [name=AA, id=1001], Person [name=BB, id=1002]]

package com.scma.Hash;

public class Person {
    String name;
    int id;
    public Person(String name, int id) {
        super();
        this.name = name;
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Person() {
        super();
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", id=" + id + "]";
    }

    @Override
    public boolean equals(Object obj) {
        if(!(obj instanceof Person)) {
            return false;
        }
        Person p = (Person) obj;
        return this.id == p.id && this.name.equals(p.name);
    }
    @Override
    public int hashCode() {
        int result = 17;
        result = result * 37 + id;
        result = result * 37 + name.hashCode();
        return result;
    }
}

HashMap

基本特性就不说了

hashMap中put

1.计算关于key的hashcode值（与Key.hashCode的高16位做异或运算）
2.如果散列表为空时，调用resize()初始化散列表
3.如果没有发生碰撞，直接添加元素到散列表中去
4.如果发生了碰撞(hashCode值相同)，进行三种判断
4.1:若key地址相同或者equals后内容相同，则替换旧值
4.2:如果是红黑树结构，就调用树的插入方法
4.3：链表结构，循环遍历直到链表中某个节点为空，尾插法进行插入，插入之后判断链表个数是否到达变成红黑树的阙值8；也可以遍历到有节点与插入元素的哈希值和内容相同，进行覆盖。
5.如果桶满了大于阀值，则resize进行扩容

hash函数的实现方式

对key的hashCode做hash操作，与高16位做异或运算
还有平方取中法，除留余数法，伪随机数法