javaSE_集合与队列(map)

比眉伴天荒 2022-05-25 03:14 242阅读 0赞

Map:健值对，健不能重，和set一样，有HashMap、LinkedHashMap、TreeMap三种。

HashMap，基于散列表实现，查找速度快（依赖hashcode()和equals()），存放元素无序。

ConcurrentHashMap，线程安全的HashMap，用于替代HashTable（线程安全，但基于整个对象的锁实现的，效率不高），而ConcurrentHashMap是采用分段加锁的方式实现，提升了效率。

LinkedHashMap，基于散列表、双向链表实现。如HashMap的查找速度，遍历时有序（默认为插入顺序，可通过构造方法设置“最近最少使用(Least Recently Used)顺序”）。

TreeMap，基于红黑树实现，存放有序（依赖Compareable）。

1) HashMap实现原理，如何解决冲突

HashMap使用Hash表，即数组\+链表的方式存储数据。

存储时，通过key.hash获取一个hash的数值，再模上hash表的长度，得到key值在hash表中的索引位置。如果此位置为空则直接添加值;如果此位置有值，则将新的key放到此位置上，同时新值对应的Entry的next指向之前的值，即在链表的头部插入数据。

优化：当数据量越来越多，链表就会越来越长，性能也就越差。HashMap里面设置了一个因子，随着Entry的sise越来越大，Entry\[\]会以一定的规则加长长度。

![20180507142012966][]

2) HashTable实现原理

它的每个方法都是synchronized类型，对hashtable的任何操作都会把整个表锁住，因此是线程安全的。当put数据时，会先计算hash值，如果此位置没有元素则直接添加，如d1，如果已有元素，会按照链表的方式将元素插入在链表的头部，如aa。

![20180507142500676][]

3) ConcurrentHashMap实现原理

内部使用Segment数组，每个Segment类似于HashTable，操作时是锁住某个Segment对象，其他线程可以并发操作其他Segment对象，因此效率要比HashTable高.

![20180507142726360][]

4) hashcode()和equals()

hashcode()和equals()即用于识别对象的身份。

在HashMap或类似的实现中，查找一个对象，是通过hashcode()返回的散列值映射到一个范围内的下标，在通过equals()比较此下标连接的链表是否存在相同的对象。

简单来说，hashcode()用于参考、快速定位（缩减范围），真正是否等于是依赖equals()。

覆盖这两个方法有什么原则呢？

equals()的覆盖，主要是基于此对象的业务。

而hashcode()的覆盖原则，详情可参见《Effective Java》的“覆盖equals时总要覆盖hashcode”一节。

有几个比较重要的原则：

1、两个equals相等的对象，其hashcode是相等的。

2、两个equals不等的对象，其hashcode有可能是相等的。

3、好的hashcode()应产生分布均匀的散列码。

和set一样，map的key值是不能重复的，如果是自定义对象，是通过hashcode和equals来判断是否为同一个对象的，因此如果以对象作为key值，需要注意这两个方法的重载。

5) LinkedHashMap的两种遍历方式

**public** **static** **void** useLinkedHashMap()\{

System.***out***.println("--LinkedHashMap根据输入的顺序输出\--");

LinkedHashMap<String, String> linkedHashMap=**new** LinkedHashMap<>();

linkedHashMap.put("3", "Value3");

linkedHashMap.put("1", "Value1");

linkedHashMap.put("2", "Value2");

linkedHashMap.put("b", "ValueB");

linkedHashMap.put("a", "ValueA");

linkedHashMap.get("2");

linkedHashMap.get("b");

Iterator lit = linkedHashMap.entrySet().iterator();

**while** (lit.hasNext()) \{

Map.Entry e = (Map.Entry) lit.next();

System.***out***.println(e.getKey() + "--" + e.getValue());

System.***out***.println("--LinkedHashMap最近最少使用排序\--");

// 初始容量、加载因子使用默认的16和0.75,排序为true

LinkedHashMap<String, String> Map2 = **new** LinkedHashMap<>(16, 0.75f, **true**);

Map2.put("3", "Value3");

Map2.put("1", "Value1");

Map2.put("2", "Value2");

Map2.put("b", "ValueB");

Map2.put("a", "ValueA");

Map2.get("b");

Map2.get("2");

Iterator lit2 = Map2.entrySet().iterator();

**while** (lit2.hasNext()) \{

Map.Entry e = (Map.Entry) lit2.next();

System.***out***.println(e.getKey() + "--" + e.getValue());

输出：

\--LinkedHashMap根据输入的顺序输出\--

3--Value3

1--Value1

2--Value2

b--ValueB

a--ValueA

\--LinkedHashMap最近最少使用排序\--

3--Value3

1--Value1

a--ValueA

b--ValueB

2--Value2

因为b和2刚使用，因此排在了最后。

6) 自定义对象之HashMap

**public** **static** **void** useCustomObjMap()\{

System.***out***.println("--HashMap使用自定义对象\--");

Map<Student, String> map = **new** HashMap<>();

map.put(**new** Student("张三", 30), "1");

map.put(**new** Student("李四", 32), "2");

map.put(**new** Student("王五", 31), "3");

map.put(**new** Student("李四", 33), "4");

Iterator iter = map.entrySet().iterator();

**while** (iter.hasNext())\{

Map.Entry e = (Entry) iter.next();

Student st = (Student) e.getKey();

System.***out***.println(st.getName() + "--" + e.getValue());

输出：

\--treeMap使用自定义对象\--

王五\--3

李四\--2

李四\--4

张三\--1

可见，有两个李四，虽然姓名一样，但是这是两个对象，因此可以重复。

如果重载student的hashcode和equals方法，以姓名为判断两对象是否相同的依据：

**public** **class** Student \{

**private** String name;

**private** Integer age;

**public** Student(String name, Integer age)\{

**this**.name = name;

**this**.age = age;

**public** String getName() \{

**return** name;

**public** **void** setName(String name) \{

**this**.name = name;

**public** Integer getAge() \{

**return** age;

**public** **void** setAge(Integer age) \{

**this**.age = age;

@Override

**public** **int** hashCode() \{

**final** **int** prime = 31;

**int** result = 1;

result = prime \* result + ((name == **null**) ? 0 : name.hashCode());

**return** result;

@Override

**public** **boolean** equals(Object obj) \{

**if** (**this** == obj)

**return** **true**;

**if** (obj == **null**)

**return** **false**;

**if** (getClass() != obj.getClass())

**return** **false**;

Student other = (Student) obj;

**if** (name == **null**) \{

**if** (other.name != **null**)

**return** **false**;

\} **else** **if** (!name.equals(other.name))

**return** **false**;

**return** **true**;

输出：

\--HashMap使用自定义对象\--

王五\--3

李四\--4

张三\--1

结论：hashMap如果以自定义对象为key值，需要注意其hashcode和equals。

7) 自定义对象之TreeMap

将上面的hashMap改为TreeMap，运行时直接报错：

**public** **static** **void** useCustomObjMap()\{

System.***out***.println("--TreeMap使用自定义对象\--");

Map<Student, String> map = **new** TreeMap<>();

map.put(**new** Student("张三", 30), "1");

map.put(**new** Student("李四", 32), "2");

map.put(**new** Student("王五", 31), "3");

map.put(**new** Student("李四", 33), "4");

Iterator iter = map.entrySet().iterator();

**while** (iter.hasNext())\{

Map.Entry e = (Entry) iter.next();

Student st = (Student) e.getKey();

System.***out***.println(st.getName() + "--" + e.getValue());

Exception in thread "main" java.lang.ClassCastException: com.gary.set.Student cannot be cast to java.lang.Comparable

说student类需要重载Comparable。

**public** **class** Student **implements** Comparable\{

**private** String name;

**private** Integer age;

**public** Student(String name, Integer age)\{

**this**.name = name;

**this**.age = age;

**public** String getName() \{

**return** name;

**public** **void** setName(String name) \{

**this**.name = name;

**public** Integer getAge() \{

**return** age;

**public** **void** setAge(Integer age) \{

**this**.age = age;

@Override

**public** **int** compareTo(Object arg0) \{

Student st = (Student) arg0;

**return** **this**.name.hashCode() - st.name.hashCode();

此时输出：

\--TreeMap使用自定义对象\--

张三\--1

李四\--4

王五\--3

结论：TreeMap使用自定义对象为key值，其类需要重载Comparable。

8) Map的遍历

有四种方法遍历：

**public** **static** **void** traverseMap()\{

HashMap<String, String> hashMap=**new** HashMap<>();

hashMap.put("3", "Value3");

hashMap.put("1", "Value1");

hashMap.put("2", "Value2");

hashMap.put("b", "ValueB");

hashMap.put("a", "ValueA");

// 方法一

System.***out***.println("------entrySet------");

**for** (Map.Entry<String, String> entry : hashMap.entrySet()) \{

System.***out***.println(entry.getKey() + "--" + entry.getValue());

// 方法二：此方法比entrySet快10%

// 遍历key

System.***out***.println("------keySet------");

**for** (String key : hashMap.keySet())\{

System.***out***.println(key);

// 遍历值

System.***out***.println("------values------");

**for** (String value : hashMap.values())\{

System.***out***.println(value);

// 方法三

// 性能和keySet的性能差不多，而且可以在循环体中调用it.remove来删除数据，上面的则不能

System.***out***.println("------iterator------");

Iterator it = hashMap.entrySet().iterator();

**while** (it.hasNext()) \{

Map.Entry e = (Map.Entry) it.next();

System.***out***.println(e.getKey() + "--" + e.getValue());

// 方法四

// 每次使用get方法取值是相当慢的

System.***out***.println("------keySet get------");

**for** (String key : hashMap.keySet())\{

System.***out***.println(key + "--" + hashMap.get(key));

综上所述，方法三使用iterator是最好的选择，速度快，而且还可以执行删除操作。

[20180507142012966]: /images/20220525/cfe79647a65642d0954aa219b8e9edce.png
[20180507142500676]: /images/20220525/da772c044ada4a34942043fd03b2f6ed.png
[20180507142726360]: /images/20220525/2e8b1cd4c1214d6a83e7a794e431d54a.png

javaSE_集合与队列(map)

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 Collection集合与Map集合体系

相关 JavaSE——遍历Map集合

相关 JavaSE 集合框架（3）- Map集合 HashMap LinkedHashMap

相关 javaSE_集合与队列（queue)

相关 javaSE_集合与队列(map)

相关 javaSE_集合与队列（list）

相关 javaSE_集合与队列（set）

相关 javase基础知识02-Collection集合,Map集合

相关 Javase之集合体系（4）之Map集合

相关 JavaSE 集合