Map

体系图

Map接口实现类的特点
1、Map 与 Collection 并列存在,用于保存具有映射关系的数据:key-value
2、Map中的key和value可以是任何引用类型的数据,会封装到HashMap$Node 对象中
3、Map中的key不允许重复,value可以重复
4、Map的key可以为null,value也可以为null,注意key为null,只能有一个。value为null可以多个
5、常用String类作为Map的key
6、key和value之间存在单向一对一的关系,通过key总能找到对应的value
7、Map存放数据的key-value,一对k-v是放在一个HashMap$Node中的,因为Node实现了Entry接口,有些书上说一对k-v就是一个Entry

Map map = new HashMap();
map.put("name","陈青青");
map.put("name1","陈青青");
map.put("name","陈平平");// key相同时,新值替换旧值
map.put(null,null);
map.put(null,"abc");// 等价替换
map.put("mol",null);
map.put(new Car(),new Person());

System.out.printLn(map);
System.out.printLn(map.get("name1"));//通过get,返回key的对应value

// 解读
//k-v 最后是 HashMap$Node node = newNode(hash,key,value,null)
//k-v 为了方便遍历,会创建 EntrySet 集合,该集合存放的元素类型Entry,而一个Entry对象就有k,v,EntrySet<Entry<k,v>> 即 :transient Set<Map.Entry<K,V>> entrySet;
//entrySet 中,定义的类型是Map.Entry , 实际上存放的还是HashMap$Node , 这是因为 HashMap$Node implements Map.Entry,即:static class Node<K,V> implements Map.Entry<K,V>
// 当把 HashMap$Node 对象,存放到 entrySet就方便遍历,因为Map.Entry 提供了getKey(),getValue()两个重要方法

Set set = map.entrySet(); 
System.out.printLn(set.getClass()); // HashMap$EntrySet
for(Object entry : set){
  System.out.printLn(entry.getClass());// HashMap$Node
  // 为了从  HashMap$Node 取出k-v
  // 1 先向下转型
  Map.Entry entry = (Map.Entry) obj;
  System.out.printLn(entry.getKey() +"-"+entry.getValue());
}

Set set1 = map.keySet();
Collection values = map.values();
Map接口的常用方法
  1. put : 添加
  2. remove : 根据键删除映射关系
  3. get: 根据键获取值
  4. size: 获取元素个数
  5. isEmpty: 判断是否为0
  6. clear: 清除
  7. containsKey: 查找键是否存在
Map map = new HashMap();
map.put("name","陈青青");
map.put("name","陈平");// 替换
map.put(null,"abc");
map.put("mol",new Book("",100));

map.remove(null); 
Object key = map.get("name");
map.size();
map.isEmpty();
map.clear();
map.containsKey("kl"); //false
Map 接口遍历方式
  1. containsKey : 查找键是否存在
  2. keySet:获取所有键
  3. entrySet:过去所有关系
  4. values: 获取所有的值
Map map = new HashMap();
map.put("name","陈青青");
map.put("name","陈平");// 替换
map.put(null,"abc");
map.put("刘家良","abc");
/****************第一组 :先取所有key ,通过key取value****************/
Set keyset = map.keySet();
// 1 增强for
for(Object  key : keyset){
  System.out.printLn(key +"-"+map.get(key))
}
// 2 迭代器
Iterator iterator = keyset.iterator();
while(iterator.hasNext()){
  Object key = iterator.next();
  System.out.printLn(key +"-"+map.get(key))
}
/****************第二组 :取所有value****************/
Collection values = map.values();
// 使用Collection遍历方法
// 1 增强for
for(Object  value : values){
  System.out.printLn(value)
}
// 2 迭代器
Iterator iterator1 = values.iterator();
while(iterator1.hasNext()){
  Object value = iterator.next();
  System.out.printLn(value)
}
// 3 普通for 不能用
/****************第三组:通过EntrySet 取k-v****************/
Set entrySet = map.entrySet();
// 1 增强for
for(Object entry : entrySet){
  //将 entry 转成 Map.Entry
  Map.Entry m = (Map.Entry) entry;
  System.out.printLn(m.getKey + "-" m.getValue())
}
// 2 迭代器
Iterator iterator2 = entrySet.iterator();
while(iterator2.hasNext()){
  Object entry = iterator.next();
  // 转成 Map.Entry 向下转型
   Map.Entry m = (Map.Entry) entry;
   System.out.printLn(m.getKey + "-" m.getValue()); 
}

HashMap
  1. Map接口的常用实现类: HashMap、Hashtable 和 Properties
  2. HashMap是Map接口使用频率最高的实现类
  3. HashMap是以 key-value的方式存储数据(HashMap$Node类型)
  4. Key不能重复,但是值可以,允许使用null键和null值
  5. 若添加相同key,则会覆盖原来k-V,等同于修改(K不变,V替换)
  6. 与HashSet一样,不保证映射的顺序,因为底层是以hash表的方式存储
  7. HashMap没有实现同步,因此线程不安全
HashMap底层机制

扩容机制(hashSet相同)

  1. HashMap底层维护了Node类型的数组table,默认为null
  2. 当创建对象时,将加载因子(laodfactor)初始化为0.75
  3. 当添加key-val时,通过key的哈希值得到在table的索引。然后判断该索引处是否有元素。若没有直接添加,若有元素,继续判断该元素的key是否和准备加入的key相等,若相等,则直接替换val;若不等需要判断是树结构还是链表结构,做出相应处理。若添加时发现容量不够,则需要扩容
  4. 第一次添加,则需要扩容table容量为16,临界值(threshold)为12
  5. 以后再次扩容,则需要扩容table容量为原来的2倍,临界值为原来的2倍,即24,以此类推
  6. 在Java8中,如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认8),并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64),就会进行树化

源码

//源码解读
HashMap map = new HashMap();
map.put("java",10);
map.put("php",10);
map.put("java",20);
		// 1.执行构造器 new HashMap(); 初始化加载因子 loadfactor = 0.75 HashMap$Node[] table = null
    // 2.执行put 调用hash方法,计算key的hash值(h = key.hashCode())^(h>>>16)
    public V put(K key,V value){
        return putVal(hash(key),key,value,false,true);
    }
    // 3.执行 putVal
    final V putVal(int hash, K key, V value,boolean onlyIfAbsent,boolean evict){
        Node<K,V>[] tab; Node<K,V> p; int n,i; //定义辅助变量
        // table 就是HashMap的一个数组,类型Node[]
        // 若table是null,或者 大小 = 0 ,就是第一次扩容,到16个空间
        if((tab = table) == null ||(n = tab.length) == 0){
            n = (tab = resize()).length; // resize()
        }
        // 根据key,得到hash 去计算该key应该存放到table表的哪个索引位置
        // 并且把这个位置的对象,赋给 p
        // 判断 p 是否为空,若空表示未存放数据,就创建一个node
        // 存放tab[i] = newNode(hash,key,value,null);
        if((p = tab[i=(n-1) & hash]) == null){
            tab[i] = newNode(hash,key,value,null);
        }else{
            Node<K,V> e; K k; //定义辅助变量
            // 若当前索引位置对应链表对应第一个元素和准备添加的key的hash一样
            // 并且满足,以下两个条件就不能加入:
            // (1)准备加入的key和p 指向的Node节点的key是同一个对象
            // (2)p指向的node节点的key的equals 和准备加入的key内容相同
            if(p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
                e = p;
            }else if(p instanceof TreeNode){
                //再判断p是不是一颗红黑树
                //如果是,就调用putTreeVal(),进行添加
                e = ((TreeNode<K,v>p)).putTreeVal(this,tab,hash,key,value);
            }else{
                //若当前table对应索引位置,已经是一个链表,就是用for循环比较
                for(int binCount = 0;;++binCount){
                    //依次和该链表的每一个元素比较后,都不相同,就挂载该链表的最后
                    if((e = p.next) == null){
                        p.next = newNode(hash,key,value,null);
                        // 元素添加到链表后,立即判断该链表是否已经达到8个节点
                        // 就调用treeifyBin(),对当前链表进行树化(红黑树)
                        // 在转红黑树时,进行判断,
                        // if(tab == null ||(n= tab.length) < MIN_TREEIFY_CAPACITY){resize()}
                        // 成立就扩容,否则才进行红黑树
                        if(binCount >= TREEIFY_THRESHOLD -1){
                            treeifyBin(tab,hash);
                        }
                        break;
                    }
                    //比较过程中有相同,就直接break
                    if(e.hash == hash && ((k =  e.key) == key || (key != null && key.equals(k)))){
                        break;
                    }
                    p = e;
                }
            }
            if(e != null){
                V oldValue = e.value;
                if(!onlyIfAbsent || oldValue == null){
                    e.value = value;
                }
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // size 就是每加入一个节点node,size就会++
        if(++size > threshold){
            resize();
        }
        afterNodeInsertion(evict);
        return null;
    }
  //4.关于树化
  //如果table 为 null,或者大小还没有到64 ,暂时不树化,而是继续扩容
  //否则才会真正的树化 -> 剪枝
    final void treeifyBin(Node<K,V>[] tab, int hash){
      int n,index; Node<K,V> e;
      if(tab == null || (n=tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    }
Hashtable

基本介绍

  1. 存放的元素时键值对:K-V
  2. Hashtable的键和值都不能为null
  3. Hashtable的使用方法基本与hashMap一样
  4. Hashtable是线程安全的,hashMap是线程不安全

底层结构

Hashtable table = new Hashtable();
table.put("john",12);
table.put(null,12); // 异常
table.put("john",null); // 异常
table.put("john",100);
//
//1、底层有数组 Hashtable$Entry[] 初始化大小为 11
//2、临界值 threshold 8 = 11 * 0.75
//3、扩容 :按照自己扩容机制进行
//4、执行 addEntry(hash,key,value,index)
//5、当 if(count >= threshold) 满足时,就进行扩容
//6、按照 int newCapacity = (oldCapacity << 1) + 1 的大小扩容

Properties

Properties继承自Hashtable类并且实现了Map接口,也是使用一种键值对的形式保存数据

使用特点和Hashtable类似

Properties 还可以用于 xxx.properties 文件中,加载数据到Properties类对象,并进行读取和修改

工作中,xxx.properties 文件通常作为配置文件

Properties properties = new Properties();
// 增/改
properties.put(".johe",22);
properties.put("lucy",100);
properties.put(".je",22);
properties.put(".je",1999);
// 查
properties.get("lucy");
// 删
properties.remove("lucy");
TreeSet
// 当使用无参构造,创建TreeSet,仍是无序的
TreeSet treeSet = new TreeSet();
// 使用TreeSet 提供的构造器,可以传入比较器,并指定排序规则
TreeSet treeSet = new TreeSet(new Comparator(){
  // 按字符排序
  @Override
  public int compare(Object o1, Object o2){
    return ((String) o1).compareTo((String) o2);
  }
});
// 添加数据
treeSet.add("jack");
treeSet.add("tom");
treeSet.add("ssp");

System.out.printLn(treeSet);

//解读
// 构造器把传入的比较器对象,赋给了 TreeSet底层的 TreeMap 的属性 this.comparator
/*
public TreeMap(Comparator<? super K> comparator){
	this.comparator = comparator;
}
再调用 treeSet.add(),在底层会执行到
if(cpr != null){ // cpr 匿名内部类(对象)
	do{
		parent = t;
		// 动态绑定内部类 compare
		cmp = cpr.compare(key,t.key);
		if(cmp < 0 )
			t = t.left;
		else if(cmp > 0)
			t = t.right;
		else
			return t.setValue(value);// 若相等 数据加入不了
	} while(t != null)
}
*/
TreeMap
// 使用默认构造器,不排序
TreeMap treeMap  = new TreeMap();
// 使用TreeSet 提供的构造器,可以传入比较器,并指定排序规则
TreeMap treeMap = new TreeMap(new Comparator(){
  // 1 按字符大小排序
  @Override
  public int compare(Object o1, Object o2){
    return ((String) o1).compareTo((String) o2);
  }
  // 2 按字符长度的大小排序
  @Override
  public int compare(Object o1, Object o2){
    return ((String) o1).length()- ((String) o2).length();
  }
});
treeMap.put("jack","杰克");
treeMap.put("tom","汤姆");
System.out.printLn(treeMap);

//解读
/*
1 构造器把传入的比较器对象,赋给了 TreeSet底层的 TreeMap 的属性 this.comparator
public TreeMap(Comparator<? super K> comparator){
	this.comparator = comparator;
}
2 调用 put方法
	2.1 第一次添加,把k-v 封装到Entry对象中
	Entry<K,V> t = root;
	if(t == null){
		compare(key,key);
		root = new Entry<>(key,value,null);
		size = 1;
		modCount++;
		return null;
	}
	2.2 以后添加
	Comparator<? super K> cpr = comparator;
	if(cpr != null){ // cpr 匿名内部类(对象)
	do{
		parent = t;
		// 动态绑定内部类 compare
		cmp = cpr.compare(key,t.key);
		if(cmp < 0 )
			t = t.left;
		else if(cmp > 0)
			t = t.right;
		else
			return t.setValue(value);// 若相等 数据加入不了
	} while(t != null)
}
*/

开发中如何选择集合实现类

在开发中,选择什么集合实现类,主要取决于业务操作特点,然后根据集合实现类特性进行选择:

  1. 先判断存储的类型(一组对象或一组键值对)

  2. 一组对象[单列]:Collection 接口

    ​ 允许重复 :List

    ​ 增删多 :LinkedList 【底层维护一个双向链表】

    ​ 改查多:ArrayList 【底层维护Object类型的可变数组】

    ​ 不允许重复:Set

    ​ 无序 :HashSet 【底层HashMap,维护了一个哈希表(数组+链表+红黑树)】

    ​ 排序 :TreeSet 【插入和取出顺序一致:LinkedHashSet ,维护数组 + 双向链表】

  3. 一组键值对[双列]: Map 接口

​ 键无序 : HashMap 【底层哈希表】

​ 键有序 :TreeMap【插入和取出顺序一致:LinkedHashMap 】

​ 读取文件: Properties

版权声明:本文为MrGeng原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/MrGeng/p/16446460.html