Java--Map和HashMap基础

╰+哭是因爲堅強的太久メ 2023-10-02 13:42 29阅读 0赞

### 一、Map常用方法 ###

1、Map集合在 java.util.Map 包下，Map集合以键值对 key和value 的方式存储数据

key和value都是引用数据类型；都是存储对象的内存地址

2、Map接口中常用方法：

V put(K key, V value) 向Map集合中添加键值对
    
        V get(Object key) 通过key获取value
    
        void clear()     清空Map集合
    
        boolean containsKey(Object key) 判断Map中是否包含某个key
    
        boolean containsValue(Object value) 判断Map中是否包含某个value
    
        boolean isEmpty()    判断Map集合中元素个数是否为0
    
        V remove(Object key) 通过key删除键值对
    
        int size() 获取Map集合中键值对的个数
    
        Collection<V> values() 获取Map集合中所有的value，返回一个Collection
    
        Set<K> keySet() 获取Map集合所有的key（所有的键是一个set集合）
    
        Set<Map.Entry<K,V>> entrySet() 将Map集合转换成Set集合
    
    Map集合通过entrySet()方法转换成的这个Set集合，Set集合中元素的类型是 Map.Entry<K,V>（可以理解为一个对象）；Map.Entry是静态内部类，是Map中的静态内部

### 二、Map集合遍历 ###

Map集合遍历有两种方法

1、通过Set<K> keySet() 方法获取Map集合所有的key，然后通过key获取value

2、通过Set<Map.Entry<K,V>> entrySet()方法获取泛型对象为 Map.Entry<K,V> 的Set集合，然后使用foreach遍历，每次取出 Map.Entry<K,V> 对象的 key和value

相对来说第二种效率更高一些，直接拿到Map.Entry<K,V> 对象的属性值；而第一种还需要遍历Key获取值，本身就耗时

public static void main(String[] args) {
            Map<Integer,String> map = new HashMap<>();
            map.put(1,"张三");
            map.put(2,"李四");
            map.put(3,"王二");
    
            System.out.println("1、获取Key集合，通过key获取value");
    
            /**---- 集合遍历 ----*/
            /**
             * 1、获取Key集合，通过key获取value
             * */
            Set set = map.keySet();
            Iterator<Integer> it = set.iterator();
            while (it.hasNext()){
                Integer key = it.next();
                System.out.println("Key:" + key + "；" + "Value:" + map.get(key));
            }
    
            System.out.println("====================================================");
            System.out.println("2、拿到map中一个集合对象，遍历对象取出 key-value");
    
            /**
             * 2、拿到Map中的Set集合，集合中元素是Map.Entry；遍历Set集合取出Map.Entry对象的 key-value
             *
             * for each效率较高，直接拿到对象的属性值，不需要通过 下标索引 和 key 去查询
             * */
            Set<Map.Entry<Integer, String>> set1 = map.entrySet();
            for (Map.Entry<Integer, String> map1: set1) {
                System.out.println("Key:" + map1.getKey() + "；" + "Value:" + map1.getValue());
            }
        }

当然，还有一些其他扩展方法遍历，要看使用场景，相对来说上面两种用法最常见

如 ：

3、在for循环中遍历key或者values，一般适用于只需要map中的key或者value时使用，在性能上比使用entrySet较好

Map <String,String>map = new HashMap<String,String>();
    map.put(1, "棕色");
    map.put(2, "黄色");
    //key
    for(String key : map.keySet()){
        System.out.println(key);
    }
    //value
    for(String value : map.values()){
        System.out.println(value);
    }

4、通过Iterator遍历

Iterator<Entry<String, String>> entries = map.entrySet().iterator();
    while(entries.hasNext()){
        Entry<String, String> entry = entries.next();
        String key = entry.getKey();
        String value = entry.getValue();
        System.out.println(key+":"+value);
    }

总结：

1、entrySet的方式整体都是比keySet方式要高一些

2、单纯的获取key来说，两者的差别并不大，但是如果要获取value，还是entrySet的效率会更好，因为keySet需要从map中再次根据key获取value，而entrySet一次都全部获取出来

3、iterator的迭代器方式比foreach的效率高

注：

foreach的语法只是对iterator进行了简单的包装，使用起来更加方便而已，但是如果在foreach循环体内，对集合元素进行删除添加操作的时候，会报出ConcurrentModificationException，并报修改异常。如果需要在遍历集合的时候对象集合中元素进行删除操作，需要使用iterator的遍历方式，iterator自带的remove删除方式不会报出异常

### 三、Map集合为何无序不可重复 ###

我们以HashMap集合为例

HashMap集合：

1、**HashMap**集合底层是**哈希表/散列表**的数据结构

2、HashMap集合底层的源代码：

public class HashMap{
          // HashMap底层实际上就是一个数组（一维数组）
          Node<K,V>[] table;
    
          // 静态的内部类HashMap.Node
          static class Node<K,V> implements Map.Entry<K,V> {
              final int hash;      // 哈希值（哈希值是key的hashCode()方法的执行结果；hash值通过哈希函数/算法，可以转换存储成数组的下标）
    
              final K key;         // 存储到Map集合中的那个key
    
              V value;             // 存储到Map集合中的那个value
    
              Node<K,V> next;      // 下一个节点的内存地址。
          }
    }

3、**哈希表**是一个数组和单向链表的结合体

数组：在查询方面效率很高，随机增删方面效率很低

**单向链表**：在随机增删方面效率较高，在查询方面效率很低

哈希表将以上的两种数据结构融合在一起，充分发挥它们各自的优点

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWluZ2dlUWluZ2NodW4_size_13_color_FFFFFF_t_70_g_se_x_16][]

同一个单向链表上所有节点的hash相同，因为他们的数组下标是一样的；但同一个链表上k和k的equals方法肯定都不相等，返回false

（1）**map.put(k,v)** 实现原理：

先将k，v封装到Node对象当中

底层会调用k的hashCod( )方法得出hash值，然后通过哈希函数/哈希算法，将hash值转换成

数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上

如果说下标对应的位置上有链表，此时会拿着 k 和链表上每一个节点中的 k 进行equals()比较

如果所有的equals方法返回的都是false ，那么这个新节点 Node 将会被添加到链表的末尾

如果其中有一个 k 的 equal返回了true，那么这个节点的value将会被覆盖

（2）**v = map.get(k)** 实现原理：

先调用k的hashCode0方法得出哈希hash值，通过哈希算法转换成数组下标，通过数组下标快

速定位到某个位置上

如果这个位置上什么也没有，返回null

如果这个位置上有单向链表，那么会拿着参数 k 和单向链表上的 每个节点中的k进行equals

如果所有equals方法返回 false，那么get方法返回null

只要其中有一个节点的 k 和参数k equals的时候返回true ，那么此时这个节点的 value就是要

找的value ，get方法最终返回这个要找的value

4、HashMap集合的key部分特点： **无序，不可重复**

（1）无序：

不确定挂到哪一个单向链表

（2）不可重复：

equals方法来保证HashMap集合的key不可重复。 如果key重复了，value会覆盖。 放在HashMap集合key部分的元素其实就是放到HashSet集合中了（所以HashSet集合中的元素也需要同时重写hashCode() + equals()方法）

/** Map存储元素特点：无序不可重复 */
            // Integer是key，它的hashCode和equals都重写了。
            Map<Integer,String> map = new HashMap<>();
            map.put(11, "str11");
            map.put(22, "str22");
            map.put(33, "str33");
            map.put(44, "str44");
            map.put(55, "str55");
            map.put(66, "str66");
            map.put(66, "str86");//key重复的时候value会自动覆盖。
    
            System.out.println(map.size()); // 6
    
            // 遍历Map集合
            Set<Map.Entry<Integer,String>> set = map.entrySet();
            for(Map.Entry<Integer,String> entry : set){
                // 验证结果：HashMap集合key部分元素：无序不可重复。
                System.out.println(entry.getKey() + "=" + entry.getValue());
                /*
                33=str33
                66=str86
                22=str22
                55=str55
                11=str11
                44=str44
                * */
            }

5、散列分布均匀OR不均匀

（1）散列分布均匀

假设有100个元素，10个单向链表，那么每个单向链表上有10个节点，这是最好的情况， 是散列分布均匀的

（2）散列分布不均匀

假设将所有的hashCode()方法返回值固定为某个值，导致底层哈希表变成了 纯单向链表。这种情况我们成为：散列分布不均匀。

假设将所有的hashCode()方法返回值都设定为不一样的值，导致底层哈希表就成为一维数组了，没有链表的概念了， 也是散列分布不均匀

6、HashMap集合的默认初始化容量是16，默认加载因子是0.75 这个默认加载因子是当HashMap集合底层数组的容量达到75%的时候，数组开始扩容。 HashMap集合初始化容量必须是2的倍数，这也是官方推荐的， 这是因为达到散列均匀，为了提高HashMap集合的存取效率

/**
         * The default initial capacity - MUST be a power of two.
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /**
         * The maximum capacity, used if a higher value is implicitly specified
         * by either of the constructors with arguments.
         * MUST be a power of two <= 1<<30.
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * The load factor used when none specified in constructor.
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

综上：

放在HashMap集合key部分的元素，以及放在HashSet集合中的元素，需要同时重写hashCode()和equals()方法

### 四、HashMap重写equals()和hashCode()方法 ###

Java中对于eqauls方法和hashCode方法是这样规定的：

（1）如果两个对象相同（equals方法返回true，比较对象内容完全相同），那么它们的hashCode值一定要相同

（2）如果两个对象的hashCode相同，它们并不一定相同

关于“==”和 equals（）方法可参考

[Java--“==”和 equals（）方法\_MinggeQingchun的博客-CSDN博客][Java--_ equals_MinggeQingchun_-CSDN]

因此，equals 方法被覆盖/重写过，则 hashCode 方法也必须被覆盖/重写

测试如下，创建一个People类（只重写equals()方法），一个Person类（equals()和hashCode()方法都重写）

public class People {
        private String name;
    
        public People() {
        }
    
        public People(String name) {
            this.name = name;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        @Override
        //比较内容是否相等
        public boolean equals(Object obj){
            if (obj == null || !(obj instanceof People)) return false;
            if (this == obj) return true;
            People people = (People) obj;
            return  (this.name.equals(people.name));
        }
    }

Person类

import java.util.Objects;
    
    public class Person {
        private String name;
    
        public Person() {
        }
    
        public Person(String name) {
            this.name = name;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        /**
         * 比较名字相同
         * */
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;
            return name.equals(person.name);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(name);
        }
    }

测试代码如下，且注释后都给出了控制台上的输出结果

public static void main(String[] args) {
    
            /** People只重写了 equals()方法 */
            People people1 = new People("张三");
            People people2 = new People("张三");
    
            /**
             * 未重写 equals()方法 之前，调用根类 Object的equals()方法，
             *     public boolean equals(Object obj) {
             *         return (this == obj);
             *     }
             * 此时 “==”双等号 比较的是内存地址是否相等，new 两个对象，内存地址不同
             *
             * 重写 equals()方法 之后，比较的是内容是否相等
             * */
            System.out.println("people1和people2是否相等：" + people1.equals(people2));//true
    
            System.out.println("people1的hashCode：" + people1.hashCode());//460141958
            System.out.println("people2的hashCode：" + people2.hashCode());//1163157884
    
            Set<People> peopleSet = new HashSet<>();
            peopleSet.add(people1);
            peopleSet.add(people2);
            System.out.println("peopleSet元素个数：" + peopleSet.size());//2
    
            System.out.println("======================================");
    
            /** Person重写了 equals() 和 hashCode()方法 */
            Person person1 = new Person("李四");
            Person person2 = new Person("李四");
    
            System.out.println("person1和person2是否相等：" + person1.equals(person2));//true
    
            System.out.println("person1的hashCode：" + person1.hashCode());//842092
            System.out.println("person2的hashCode：" + person2.hashCode());//842092
    
            Set<Person> personSet = new HashSet<>();
            personSet.add(person1);
            personSet.add(person2);
            System.out.println("personSet元素个数：" + personSet.size());//1
        }

我们会发现People类只重写equals()方法没有重写hashCode()方法，导致Set集合中存放了两个元素，Person类既重写equals()方法又重写hashCode()方法，Set集合中只能存放一个值，认为person1和person2相等，hashCode也是相等的

1、**hashCode()****介绍**

hashCode() 的作用是获取哈希码，也称为散列码；它实际上是返回一个int整数。这个哈希码的作用是确定该对象在哈希表中的索引位置。hashCode() 定义在JDK的Object.java中，这就意味着Java中的任何类都包含有hashCode()函数

**2、****hashCode作用**

**以****“HashSet** **如何检查重复****”****为例**

当你把对象加入 HashSet 时，HashSet 会先计算对象的 hashcode 值来判断对象加入的位 置，同时也会与其他已经加入的对象的 hashcode 值作比较，如果没有相符的hashcode， HashSet会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让 其加入操作成功。如果不同的话，就会重新散列到其他位置。（摘自我的Java启蒙书《Head first java》第二版）。这样就大大减少了 equals 的次数，相应就大大提高了执行速度

3、向Map集合中存，以及从Map集合中取，都是先调用key的hashCode方法，然后再调用equals方法！ equals方法有可能调用，也有可能不调用

（1）put(k,v)

k.hashCode()方法返回哈希值，哈希值经过哈希算法转换成数组下标。数组下标位置上如果是null，equals不需要执行。

（2）get(k)

k.hashCode()方法返回哈希值，哈希值经过哈希算法转换成数组下标。数组下标位置上如果是null，equals不需要执行。

4、对于哈希表数据结构来说：

（1）如果o1和o2的hash值相同，一定是放到同一个单向链表上

（2）如果o1和o2的hash值不同，但由于哈希算法执行结束之后转换的数组下标可能相同（“**哈希碰撞**”）

### 五、HashMap的key和value都能为null ###

**HashMap的key和value都允许为null**

HashMap集合的key 为null值只能有一个，之后的会覆盖

**Hashtable**的key和value都是不能为null的

public static void main(String[] args) {
    
            Map map = new HashMap();
    
            // HashMap集合允许key为null
            map.put(null, null);
            System.out.println(map.size()); // 1
    
            // key重复的话value是覆盖！
            map.put(null, 100);
            System.out.println(map.size()); //1
    
            // 通过key获取value
            System.out.println(map.get(null)); // 100
        }

### 六、Hash碰撞 ###

如果两个不同的元素，通过哈希函数得出的实际存储地址相同；也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。（HashMap 通常会用一个指针数组（ table\[\]）来做分散所有的 key，当一个 key 被加入时，会通过 Hash 算法通过 key 算出这个数组的下标 i，然后就把这个 插到 table\[i\] 中，如果有两个不同的 key 被算在了同一个 i，那么就叫冲突，又叫碰撞，这样会在 table\[i\] 上形成一个链表）

散列表要解决的一个问题就是散列值的冲突问题，哈希冲突的解决方案有 4 种：

（1）开放定址法

开放定址法就是一旦发生了冲突，就去寻找下一块空的未被占用的散列地址，只要散列表足够大，

空的散列地址总能找到，并将记录存入。

（2）链地址法（拉链法）

将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲

突时就把该关键字链在以该单元为头结点的链表的尾部。（将相同hash值的对象组织成一个链表放在hash值对应的槽位）

（3）再哈希法

当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。

（4）建立公共溢出区

将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。

而HashMap即是采用了**链地址法**，也就是**数组+链表**的方式。

在Java 8 之前，HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。  
在Java 8中使用常量TREEIFY\_THRESHOLD来控制是否切换到平衡树来存储。目前，这个常量值是8，这意味着当有超过8个元素的索引一样时，HashMap会使用树来存储它们。

还可参考另一篇文章

[https://blog.csdn.net/MinggeQingchun/article/details/118337114][https_blog.csdn.net_MinggeQingchun_article_details_118337114]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWluZ2dlUWluZ2NodW4_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4c64a406cd3f4c4eb72a4ee785d663b4.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBATWluZ2dlUWluZ2NodW4=,size_13,color_FFFFFF,t_70,g_se,x_16
[Java--_ equals_MinggeQingchun_-CSDN]: https://blog.csdn.net/MinggeQingchun/article/details/121098319
[https_blog.csdn.net_MinggeQingchun_article_details_118337114]: http://xn--hashmap-yi9ku53sjh7sna