Collection集合框架集合map|hashmap|key|map|字符串|链表

Collection集合框架集

Java培训之Collection集合框架集

Map

Map概述

Map与Collection并列存在。用于保存具有映射关系的数据：Key-Value
Map 中的 key 和 value 都可以是任何引用类型的数据
Map 中的 key 不允许重复
key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value。
Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和Properties。
HashMap是 Map 接口使用频率最高的实现类。
允许使用null键和null值，与HashSet一样，不保证映射的顺序。

Map的常用方法：

1、添加、删除操作：

Object put(Object key,Object value)
Object remove(Object key)
void putAll(Map t)
void clear()

2、元素查询的操作：

Object get(Object key)
boolean containsKey(Object key)
boolean containsValue(Object value)
int size()
boolean isEmpty()

3、元视图的操作方法：

Set keySet()
Collection values()
Set entrySet()

Map的遍历

Collection集合的遍历：（1）foreach（2）通过Iterator对象遍历

Map的遍历，不能支持foreach

（1）分开遍历：单独遍历所有key，还可以根据key获取对应value

单独遍历所有value

（2）成对遍历：遍历的是映射关系Map.Entry

Map.Entry是Map接口的内部接口。每一种Map内部有自己的Map.Entry的实现类

在Map中存储数据，实际上是将Key—->value的数据存储在Map.Entry接口的实例中，再在Map集合中插入Map.Entry的实例化对象，如图示：

publicstaticvoidmain(String[] args) {

Map map =newHashMap();

map.put(“邢涛”, 60);

map.put(“林明明”, 70);

map.put(“田杰”, 80);

map.put(“李铠”, 90);

map.put(“李信”, 60);

System.out.println(“map的所有key:”);

Set keys = map.keySet();//HashSet

for(Object key : keys){

System.out.println(key+“->”+map.get(key));

System.out.println(“map的所有的value：”);

Collection values = map.values();

Iterator iter = values.iterator();

while(iter.hasNext()){

System.out.println(iter.next());

System.out.println(“map所有的映射关系：”);

//映射关系的类型是Map.Entry类型，它是Map接口的内部接口

Set mappings = map.entrySet();

for(Object mapping : mappings){

//System.out.println(mapping);

Map.Entry entry = (Map·Entry)mapping;

System.out.println(“key：”+ entry.getKey()+ “，value是：”+entry.getValue());

Map的实现类

1、HashMap

HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true，hashCode 值也相等。

HashMap 判断两个 value相等的标准是：两个 value 通过 equals() 方法返回 true。

HashMap线程不安全

JDK1.8之前：

HashMap的内部存储结构其实是数组和链表的结合。当实例化一个HashMap时，系统会创建一个长度为Capacity的Entry数组，这个长度在哈希表中被称为容量(Capacity），在这个数组中可以存放元素的位置我们称之为“桶”(bucket），每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。

每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。而且新添加的元素作为链表的head。

HashMap的扩容

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？

当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

JDK1.8之后：

HashMap的内部存储结构其实是数组和链表/树的结合。当实例化一个HashMap时，会初始化initialCapacity和loadFactor，在put第一对映射关系时，系统会创建一个长度为initialCapacity的Node数组，这个长度在哈希表中被称为容量(Capacity），在这个数组中可以存放元素的位置我们称之为“桶”(bucket），每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。

每个bucket中存储一个元素，即一个Node对象，但每一个Node对象可以带一个引用变量next，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Node链。也可能是一个一个TreeNode对象，每一个TreeNode对象可以有两个叶子结点left和right，因此，在一个桶中，就有可能生成一个TreeNode树。而新添加的元素作为链表的last，或树的叶子结点。（七上八下）

那么HashMap什么时候进行扩容和树形化呢？

当HashMap中的其中一个链的对象个数如果达到了8个，此时如果capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成TreeNode类型。当然，如果当映射关系被移除后，下次resize方法时判断树的结点个数低于6个，也会把树在转为链表。

关于映射关系的key是否可以修改？

映射关系存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算每一个Entry或Node（TreeNode）的hash值了，因此如果已经put到Map中的映射关系，再修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上。

HashSet的底层实现

publicclassHashSet

privatetransientHashMap

map;

privatestaticfinalObjectPRESENT=newObject();

publicHashSet() {

map =newHashMap<>();

publicHashSet(intinitialCapacity,floatloadFactor) {

map =newHashMap<>(initialCapacity, loadFactor);

publicHashSet(intinitialCapacity) {