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

2022-10-31
安徽
本文字数：2620 字
阅读完需：约 9 分钟

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);        }
    }}

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/a551510f8bf5b4a8e35ca5369】。文章转载请联系作者。

几分醉意.

关注

还未添加个人签名 2022-10-22 加入

还未添加个人简介

发布

暂无评论

创作场景

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

HashMap 和哈希表数据结构

同时重写 hashCode 和 equals 方法

HashMap 存储自定义类型键值

几分醉意.

评论