Java难点 | HashMap和哈希表数据结构

HashMap和哈希表数据结构

HashMap集合key部分允许null吗?
允许
但是要注意:HashMap集合的key null值只能有一个。有可能面试的时候遇到这样的问题。

HashMap集合:
1、HashMap集合底层是哈希表/散列表的数据结构。
2、哈希表是一个怎样的数据结构呢?
哈希表是一个数组和单向链表的结合体。
数组:在查询方面效率很高，随机增删方面效率很低。
单向链表:在随机增删方面效率较高，在查询方面效率很低。
哈希表将以上的两种数据结构融合在一起，充分发挥它们各自的优点。

3、最主要掌握的是:
map.put(k,v)
map.get(k)
以上这两个方法的实现原理，是必须掌握的。

4、HashMap集合的key部分特点:无序，不可重复。
为什么无序?因为不一定挂到哪个单向链表上。
不可重复是怎么保证的?equals方法来保证HashMap集合的key不可重复。如果key重复了，value会覆盖。
放在HashMap集合key部分的元素其实就是放到HashSet集合中了。所以HashSet集合中的元素也需要同时重写hashCode()+equals()

5、哈希表HashMap使用不当时无法发挥性能!
假设将所有的hashCode()方法返回值固定为某个值，那么会导致底层哈希表变成了纯单向链表。这种情况我们成为:散列分布不均匀。什么是散列分布均匀?
假设有100个元素，10个单向链表，那么每个单向链表上有10个节点，这是最好的。是散列分布均匀的。
假设将所有的hashCode()方法返回值都设定为不一样的值，可以吗，有什么问题?
不行，因为这样的话导致底层哈希表就成为一维数组了，没有链表的概念了。也是散列分布不均匀。
散列分布均匀需要你重写hashCode()方法时有一定的技巧。

同时重写hashCode和equals方法

1、向Map集合中存，以及从Map集合中取，都是先调用key的hashCode方法，然后再调用equals方法! equals方法有可能调用，也有可能不调用。
==拿put(k,v)举例，什么时候equals不会调用?==
k.hashCode()方法返回哈希值
哈希值经过哈希算法转换成数组下标。
数组下标位置上如果是null,eauals不需要执行。
==拿get(k)举例，什么时候equals不会调用?==
k.hashCode()方法返回哈希值，
哈希值经过哈希算法转换成数组下标。
数组下标位置上如果是null,equals不需要执行。

2、注意:如果一个类的equals方法重写了，那么hashCode()方法必须重写。并且equals方法返回如果是true,hashCode()方法返回的值必须一样。
equals方法返回true表示两个对象相同，在同一个单向链表上比较。那么对于同一个单向链表上的节点来说，他们的哈希值都是相同的。所以hashCode()方法的返回值也应该相同。

3、hashCode()方法和equals()方法不用研究了，直接使用IDEA工具生成，但是这两个方法需要同时生成。

4、终极结论:
放在HashMap集合key部分的，以及放在HashSet集合中的元素，需要同时重写hashCode方法和equals方法。

5、对于哈希表数据结构来说:
如果o1和o2的hash值相同，一定是放到同一个单向链表上。
当然如果o1和o2的hash值不同，但由于哈希算法执行结束之后转换的数组下标可能相同，此时会发生“哈希碰撞”。

HashMap存储自定义类型键值

HashMap存储自定义类型键值
Map集合保证key是唯一的:
作为key的元素，必须重写hashCode方法和equals方法，以保证key唯一

举例

Person类

public class Person {
    private String name;
    private int age;

    public Person() {
    }

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

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

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    public String getName() {
        return name;
    }

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

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}

主方法

public class 主方法 {
    public static void main(String[] args) {
    	show01();
        show02();
    }

    /*
        HashMap存储自定义类型键值
        key：String类型
            String类重写了hashCode和equals方法，可以保证key唯一
        value：Person类型
            value可以重复(同名同年龄的人视为同一个)
     */
    private static void show01() {
        //创建HashMap集合
        HashMap<String,Person> map =new HashMap<>();
        //往集合添加元素  key有重复会把新的value替换原来的value
        map.put("北京",new Person("张三",18));
        map.put("上海",new Person("李四",19));
        map.put("广州",new Person("王五",20));
        map.put("北京",new Person("赵六",18));
         //使用keySet加增强for遍历map集合
        Set<String> set = map.keySet();
        for (String s : set) {
            Person s1 = map.get(s);
            System.out.println(s+"-->"+s1);
        }
    }

    /*
        HashMap存储自定义类型键值
        key:Person类型
            Person类必须重写hashCode和equals方法，以保证key唯一
        value：String类型
            可以重复
     */
    private static void show02() {
        //创建HashMap集合
        HashMap<Person,String> map =new HashMap<>();
        //往集合添加元素
        map.put(new Person("女王",18),"英国");
        map.put(new Person("秦始皇",18),"秦国");
        map.put(new Person("普京",30),"俄罗斯");
        map.put(new Person("女王",18),"b国");
        //使用entryset和增强for遍历map集合
        Set<Map.Entry<Person, String>> entries = map.entrySet();
        for (Map.Entry<Person, String> entry : entries) {
            Person key = entry.getKey();
            String value = entry.getValue();
            System.out.println(key+"-->"+value);
        }

    }
}