11_6、Java集合之Map接口（包括HashMap在内的子接口）的使用

创始人

2024-05-07 14:05:07

0次

一、引入

Map与Collection并列存在。用于保存具有映射关系的数据:key-value （双列集合框架），Map 中的 key 和 value 都可以是任何引用类型的数据。Map 中的 key 用Set来存放，不允许重复，即同一个 Map 对象所对应的类，须重写hashCode()和equals()方法。key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value 。Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和 Properties。其中，HashMap是 Map 接口使用频率最高的实现类。

二、常用实现类结构

1、Map:双列结构，存储具key-value特点的数据。

可以类比：“数学中的函数” y = f(x);

1.1、HashMap:作为Map接口的主要实现类。线程不安全的，效率高；可以存储null的key和value

1.1.1、LinkedHashMap:保证在遍历Map的元素时，可以照添加的顺序进行遍历。

原因：在HashMap的基础上，添加了一对指针，分别指向前一个元素和后一个元素。对于频繁的遍历操作时，此类比HashMap的效率更高。

1.2、TreeMap:保证照添加的key-value对进行排序，实现顺序遍历。一般考虑使用key的值进行自然排序或定制排序。底层使用红黑树存储数据。

1.3、Hashtable:作为古老实现类。线程安全的，效率低。不能存储null的key和value

1.3.1、Properties:常用来处理配置文件，其key和value都是String类型。

2、HashMap的底层结构：

①、 jdk 7 及以前：数组+链表

②、jdk8：数组+链表+红黑树

3、经典面试题（高频）

①、HashMap的底层实现原理？

②、HashMap与Hashtable的异同？

三、存储结构的理解

Map中的key-value结构理解

1、Map中的key：无序的、不可重复的。使用Set存储。—>key所在的类必须重写equals()和hashCode()（以HashMap为例）。

2、Map中的value:无序的，可重复的。使用Collection存储。—>value所在的类必须重写equals()。

一个键值对：key-value构成一个Entry对象。Map中的entry：无序的，不可重复的，使用Set存储。

图示：

四、常用方法

1、添加：put(Object key,Object value)

        Map map = new HashMap();//put()map.put("AA",123);//添加map.put(45,12);map.put("CC",96);Map map1 = new HashMap();map1.put("GG",96);map1.put("FF",96);//putAll(Map m)map.putAll(map1);System.out.println(map);

2、删除：remove(Object key)

        //remove(Object key)map.remove("GG");System.out.println(map);

3、更改：put(Object key,Object value)

        map.put("AA",88);//替换覆盖

4、查询：get(Object key);

        //Object get(Object key)System.out.println(map.get("AA"));//123

5、长度：size()

        System.out.println(map.size());

6、遍历：keySet() \ values() \ entrySet()

/*元视图操作的方法：Set keySet()：返回所有key构成的Set集合Collection values()：返回所有value构成的Collection集合Set entrySet()：返回所有key-value对构成的Set集合*/@Testpublic void test5() {Map map = new HashMap();map.put("AA", 123);//添加map.put(45, 12);map.put("CC", 96);//Set keySet()Set set = map.keySet();Iterator iterator = set.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}System.out.println();//Collection values()Collection values = map.values();for(Object obj : values){System.out.println(obj);}System.out.println();//Set entrySet()Set set1 = map.entrySet();//方式1Iterator iterator1 = set1.iterator();while (iterator1.hasNext()){Object obj = iterator1.next();Map.Entry entry = (Map.Entry) obj;Object key = entry.getKey();Object value = entry.getValue();System.out.println(key  + "————>" + value);}System.out.println();//方式2Set set2 = map.keySet();Iterator iterator2 = set2.iterator();while(iterator2.hasNext()){Object key = iterator2.next();Object value = map.get(key);System.out.println(key + "===" + value);}}

五、内存结构说明（难点）

1、HashMap在jdk7中实现原理：

1.1、底层实现原理：

Map map = new HashMap();

底层创建了一个长度为16的一维数组 Entry[] table

... 此时可能已经调用过一次或多次put...

map.put(key1,value1);

首先，调用key1所在类的hashCode()方法，计算出key1的哈希值，再通过某种算法确定key1的索引：

如果当前数组索引上没有储存元素，那么key1-value1存储成功。—>情况1

如果当前数组索引上已经存储元素（存储一个或多个数据（以链表形式存在）），那么比较key1与一个或多个已存在的数据的哈希值：

如果key1与其他一个或多个数据的哈希值不相同，那么key1-value1以链表的形式添加成功。—>情况2

如果key1与某一个数据（key2-value2）的哈希值相同，那么就调用key1.equals(key2)：

如果equals()返回的false,那么key1-value1以链表的形式添加成功。—>情况3

如果equals()返回true，那么用value1替换value2的数据。（此时的put方法具有更新数据的作用）。

1. 2、补充

对于情况2与情况3，此时的key1-value1与其它数据以链表的方式存储。

1.3、扩容机制

在不断的添加过程中，涉及到扩容机制：当超出临界值（且要存储的位置非空时）扩容至原有数组长度的2倍，并将原有的数据复制到新数组。

2、HashMap在jdk8中相较于jdk7在底层实现方面的不同：

2.1、new HashMap();时，底层没有创建长度为16的数组。

2.2、底层的存储数组为Node[],而并非Entry[]。

2.3、首次调用put方法时，会创建一个长度为16的Node[]数组。

2.4、jdk7中：数组+链表；jdk8中：数组+链表+红黑树。

在HashMap中数组的某个索引上的以链表形式存在的元素个数 > 8 且当前数组长度 > 64时，此时，从索引上的所有元素改为红黑树存储。

3、HashMap底层典型属性的属性的说明：

3.1、DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16

3.2、DEFAULT_LOAD_FACTOR：HashMap的默认加载因子:0.75

3.3、threshold：扩容的临界值，=容量*填充因子 16*0.75 >=12

3.4、TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树:8

3.5、MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。64

4、LinkedHashMap的底层实现源码：

static class Entry extends HashMap.Node {Entry before, after;可以记录前一个和后一个元素，方便遍历集合Entry(int hash, K key, V value, Node next) {super(hash, key, value, next);}}

保证在遍历Map的元素时，可以照添加的顺序进行遍历。

原因：在HashMap的基础上，添加了一对指针，分别指向前一个元素和后一个元素。对于频繁的遍历操作时，此类比HashMap的效率更高。

5、TreeMap的使用

TreeMap:要求添加进TreeMap中的key-value 中的key必须是同一个类的对象。

通过key进行排序：自然排序、定制排序。

要求：与TreeSet规则类似

5.1、自然排序

①提供用于添加元素测试的类：

public class User implements Comparable {private String name;private int age;public User() {}public User(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public int getAge() {return age;}@Overridepublic boolean equals(Object o) {System.out.println("User.equals()....");if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;User user = (User) o;if (age != user.age) return false;return Objects.equals(name, user.name);}@Overridepublic String toString() {return "User{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic int hashCode() {int result = name != null ? name.hashCode() : 0;result = 31 * result + age;return result;}//按照姓名从大到小,年龄从小到大@Overridepublic int compareTo(Object o) {if(o instanceof  User){User user = (User) o;
//            return -this.name.compareTo(user.name);int compare = -this.name.compareTo(user.name);if(compare != 0){return compare;}else{return Integer.compare(this.age,user.age);}}throw new RuntimeException("数据类型不匹配");}
}

②测试代码：

//自然排序@Testpublic void test1(){TreeMap map = new TreeMap();User u1 = new User("Tom",20);User u2 = new User("Jerry",38);User u3 = new User("Jack",22);User u4 = new User("Rose",18);map.put(u1,123);map.put(u2,456);map.put(u3,789);map.put(u4,963);Set set = map.entrySet();Iterator iterator = set.iterator();while(iterator.hasNext()){Object obj = iterator.next();Map.Entry entry = (Map.Entry)obj;System.out.println(entry.getKey() + "--->" + entry.getValue());}}

测试结果：

5.2、定制排序

①测试代码：

//定制排序@Testpublic void test2(){TreeMap map = new TreeMap(new Comparator() {@Overridepublic int compare(Object o1, Object o2) {if(o1 instanceof User && o2 instanceof User){User u1 = (User) o1;User u2 = (User) o2;return -Integer.compare(u1.getAge(),u2.getAge());}throw new RuntimeException("数据类型不匹配");}});User u1 = new User("Tom",20);User u2 = new User("Jerry",38);User u3 = new User("Jack",22);User u4 = new User("Rose",18);map.put(u1,123);map.put(u2,456);map.put(u3,789);map.put(u4,963);Set set = map.entrySet();Iterator iterator = set.iterator();while(iterator.hasNext()){Object obj = iterator.next();Map.Entry entry = (Map.Entry)obj;System.out.println(entry.getKey() + "--->" + entry.getValue());}}