[数据结构与算法]Java集合（二）

15、Map接口

一、框架

*        |----Map接口：双列集合，用来存储key - value的数据 -->高中函数：y=f(x)
*        |---HashMap：作为Map的主要实现类；线程不安全的，效率高；存储null的key和value
*             |---LinkedHashMap：保证在遍历Map元素时，可以按照添加的顺序实现遍历
*                              原因：在原有的HashMap底层结构上，添加了一对指针，用来指向前一个数据和后一个数据
*                              对于频繁的遍历操作，此类执行效率高于HashMap。
*        SortedMap接口：TreeMap：保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序和定制排序。底层使用红黑树
*        |---Hashtable：作为Map的古老实现类；线程安全的，效率低；不能存储null的key和value
*             |---Properties：常用来处理配置文件。key和value都是String类型
*      HashMap的底层：数组+链表（jdk7及以前）
*                      数组+链表+红黑树（jdk8）

二、Map的结构理解

• Map中的key：无序的，不可重复的，使用Set存储所有的key —> 要求key所在类重写equals()和hashCode()（以HashMap为例）
• Map中的value：无序的，可重复的，使用Collection存储所有的value—>value所在类要重写equals()
• 一个键值对：key-value构成了一个Entry对象。
• Map中的entry：无序的，不可重复的，使用Set存储所有的entry。

三、HashMap底层实现原理：jdk7为例：

* HashMap map = new HashMap();
* 在实例化以后，底层创建了一个长度16的一维数组Entry[] table。
* ...可能已经执行过多次put...
* map.put(key1,value1);
* 首先：调用key1所在类的hashCode()计算key1的哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置
* 如果此位置上的数据为空，此时的key1-value1添加成功。---情况一
* 如果此位置上的数据不为空，（意味着此位置上存在一个或多个数据（以链表的形式存在）），
* 比较key1和已经存在的一个或多个数据的哈希值：
*      如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功。---情况二
*      如果key1的哈希值与已经存在的某一个数据（key2-value2）的哈希值相同，继续比较，调用key1所在类的equals()方法，比较：
*              如果equals()返回false：此时key1-value1添加成功。---情况三
*              如果equals()返回true：使用value1替换value2.
*
*     补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。
*     在不断补充的过程中，会涉及到扩容问题，当超出临界值（且存放的位置非空）时，
*     默认扩容方式：扩容为原来的2倍，并将原来的数据复制过来。
*
*  jdk8情况下：
*      jdk8相较于jdk7在底层实现方面的不同：
*      1、new HashMap()：底层没有创建一个长度为16的数组。
*      2、jdk8底层的数组是Node[]，而非Entry[]
*      3、首次调用put()方法时，底层创建长度为16的数组。
*      4、原来jdk7底层结构只有：数组+链表。   jdk8中底层结构：数组+链表+红黑树。
        *jdk7(新的元素指向旧的元素) jdk8(旧的元素指向新的元素。)
*          *当数组的某一个索引位置上的元素以链表形式存在的数据个数 >8  且当前数组的长度 >64时，
*          *此时此索引位置上的所有数据改为红黑树存储。
*
*  DEFAULT_INITIAL_CAPACITY：HashMap的默认容量：16
*  DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
*  threshold：扩容的临界值，=容量*加载因子：16*0.75=>12
*  TREEIFY_THRESHOLD：Bucket中，链表长度大于该默认值，转化为红黑树：8
*  MIN_TREEIFY_CAPACITY：桶中的Node被树化时最下的hash表容量：64
*
*  四、LinkedHashMap的底层实现原理：

*     源码：
*     static class Entry<K,V> extends HashMap.Node<K,V> {
*         Entry<K,V> before, after;//能够记录添加的元素的先后顺序。
*         Entry(int hash, K key, V value, Node<K,V> next) {
*             super(hash, key, value, next);
*         }
*     }

HashMap常用方法：

V     put(K key, V value):将制定key-value添加到（或修改）当前map对象中
void  putAll(Map<? extends K,? extends V> m)：将Map集合m添加到当前map对象中
V     remove(Object key)：移除指定key的key—value对，并返回value
void  clear()：清空当前map中的所有的数据
Map map = new HashMap();
//添加
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
//修改
map.put("AA",87);
System.out.println(map);//{AA=87, BB=56, 45=123}
Map map1 = new HashMap();
map1.put("CC",56);
map1.put("BB",90);
map.putAll(map1);
System.out.println(map);//{AA=87, BB=90, CC=56, 45=123}
System.out.println(map.remove(45));//123
System.out.println(map);//{AA=87, BB=90, CC=56}
map.clear();
System.out.println(map);//{}
/*
元素查询：
V     get(Object key)：获取指定key对应的value；当前map集合中没有指定的key时返回null
boolean     containsKey(Object key)：是否包含指定的key
boolean     containsValue(Object value)：是否包含指定的value
int   size()：返回map中key-value对的个数
boolean     isEmpty()：判读当前map是否为空
*/
Map map = new HashMap();
//添加
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
Object value = map.get("BB");//当map集合中没有指定的key时返回null
System.out.println(value);//56
System.out.println(map.containsKey("BB"));//true
System.out.println(map.containsValue(123));//true
System.out.println(map.size());//3
System.out.println(map.isEmpty());//false
/*
元视图操作的方法：
Set KeySet()：返回所有key构成的Set集合
Collection<V>     values()：返回所有value构成的Collection集合
Set<Map.Entry<K,V>>     entrySet()：返回所有key-value对构成的Set集合
*/
Map map = new HashMap();
//添加
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
Set set = map.keySet();
System.out.println(map);//{AA=123, BB=56, 45=123}
System.out.println(set);//[AA, BB, 45]
Collection coll = map.values();
System.out.println(coll);//[123, 56, 123]
Set set1 = map.entrySet();//都是Map.Entry类型
System.out.println(set1);//[AA=123, BB=56, 45=123]
for (Object obj : set1){
    Map.Entry entry = (Map.Entry) obj;
    System.out.println(entry.getKey()+"---"+entry.getValue());
}
for (Object obj :set1){
    System.out.println(obj);
}

TreeMap实现类

//向TreeMap中添加key-value，要求key必须是由用一个类创建的对象
//因为要按照key进行排序：自然排序、定制排序

定制排序代码演示：

    @Test
    public void test2(){
        Comparator com = new Comparator(){
            //按照年龄从小到大排列
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Person && o2 instanceof Person){
                    Person p1 = (Person) o1;
                    Person p2 = (Person) o2;
                    return Integer.compare(p1.getAge(),p2.getAge());
                }else
                    throw new RuntimeException("数据类型不匹配");
            }
        };
        TreeMap map = new TreeMap(com);
        map.put(new Person("Tom",12),1001);
        map.put(new Person("Jerry",18),1009);
        map.put(new Person("Peter",10),1030);
        map.put(new Person("Anne",17),1005);
        map.put(new Person("Anne",19),1005);
        Set set = map.entrySet();
        for (Object o : set ){
            System.out.println(o);
        }
        /*
        Person[name='Peter', age=10]=1030
        Person[name='Tom', age=12]=1001
        Person[name='Anne', age=17]=1005
        Person[name='Jerry', age=18]=1009
        Person[name='Anne', age=19]=1005
         */
    }

Collections工具类的使用：

/*
* [Collections :操作Collection、Map的工具类]
*面试题：Collection 和 Collections 的区别？
* Collection是一个操作单列数据的集合
* Collection是一个操作Collection 和Map 的工具类，Collections中所有方法都是static的
*/
//工具类的常用方法：
public class CollectionsTest {
    /*
    排序方法（均为static）
    reverse(List):反转List中元素的顺序
    shuffle(List):对List集合元素进行随机排序
    sort(List):根据元素的自然排序对指定List集合元素按升序排序
    sort(List,Comparator):根据指定的Comparator产生的顺序对List集合元素进行排序
    swap(List list,int i,int j):将指定list集合中的i处元素和j处元素进行交换
     */
    @Test
    public void test1(){
        ArrayList coll = new ArrayList();
        coll.add("AA");
        coll.add(123);
        coll.add(new Date());
        coll.add(new String("Tom"));
        System.out.println(coll);//[AA, 123, Sun Aug 22 21:52:16 CST  2021, Tom]
        Collections.reverse(coll);
        System.out.println(coll);//[Tom, Sun Aug 22 21:52:16 CST 2021,  123, AA]
        Collections.swap(coll,0,coll.size()-1);
        System.out.println(coll);//[AA, Sun Aug 22 22:03:31 CST 2021,  123, Tom]
        Collections.shuffle(coll);//随机排序
        System.out.println(coll);//
        System.out.println("***************************");
        List list = new ArrayList();
        list.add(123);
        list.add(3);
        list.add(-23);
        list.add(83);
        list.add(0);
        Collections.sort(list);
        System.out.println(list);//[-23, 0, 3, 83, 123]
        Comparator com = new Comparator() {
            //按照年龄从小到大排列
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Person && o2 instanceof Person){
                    Person p1 = (Person) o1;
                    Person p2 = (Person) o2;
                    return Integer.compare(p1.getAge(),p2.getAge());
                }else
                    throw new RuntimeException("数据类型不匹配");
            }
        };
        List ls = new ArrayList();
        ls.add(new Person("Tom",22));
        ls.add(new Person("Jum",38));
        ls.add(new Person("Jerry",38));
        ls.add(new Person("Jack",14));
        ls.add(new Person("Ange",31));
        ls.add(new Person("Ange",32));
        Collections.sort(ls,com);
        for (Object p : ls){
            System.out.println(p);
        }
    }
    /*
    查找、替换
    Object max(Collection):根据元素的自然排序，返回给定集合的最大元素
    Object max(Collection,Comparator):根据Comparator指定的顺序，返回给定集合的最大元素
    Object min(Collection):根据元素的自然排序，返回给定集合的最小元素
    Object min(Collection,Comparator)；根据Comparator指定的顺序，返回给定集合的最小元素
    int frequency(Collection,Object):返回指定集合中指定元素的出现次数
    void copy(List dest,List src):将src中的内容复制到dest中
    boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换List对象的所有旧值
     */
    @Test
    public void test2(){
        List list = new ArrayList();
        list.add(123);
        list.add(3);
        list.add(-23);
        list.add(83);
        list.add(0);
        System.out.println(Collections.max(list));//123
        System.out.println(Collections.min(list));//-23
        System.out.println("*****************");
        Comparator com = new Comparator() {
            //按照年龄从小到大排列
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Person && o2 instanceof Person){
                    Person p1 = (Person) o1;
                    Person p2 = (Person) o2;
                    return Integer.compare(p1.getAge(),p2.getAge());
                }else
                    throw new RuntimeException("数据类型不匹配");
            }
        };
        List ls = new ArrayList();
        ls.add(new Person("Tom",22));
        ls.add(new Person("Jum",39));
        ls.add(new Person("Jerry",38));
        ls.add(new Person("Jack",14));
        ls.add(new Person("Ange",31));
        ls.add(new Person("Ange",31));
        System.out.println(Collections.max(ls,com));//Person[name='Jum',  age=39]
         System.out.println(Collections.min(ls,com));//Person[name='Jack',  age=14]
        System.out.println(Collections.frequency(ls,new  Person("Ange",31)));//2
        System.out.println("****************");
        //java.lang.IndexOutOfBoundsException: Source does not fit in  dest
        //List l= new ArrayList();
        //Collections.copy(l,ls);
        List dest = Arrays.asList(new Object[ls.size()]);
        Collections.copy(dest,ls);
        for (Object p : dest){
            System.out.println(p);
        }
        System.out.println();
        Collections.replaceAll(dest,new Person("Ange",31),123);
        for (Object p : dest){
            System.out.println(p);
        }
    }
    @Test
    public void test3(){
        /*
        Collections类中提供了多个synchronizedXxx()方法，
        该方法科使将指定集合包装成线程同步的集合，从而可以解决
        多线程并发访问结婚是的线程安全问题
         */
        List list = new ArrayList();
        list.add(123);
        list.add(3);
        list.add(-23);
        list.add(83);
        list.add(0);
        //返回的list1即为线程安全的List
        List list1 = Collections.synchronizedList(list);
    }
}

END
课程笔记
尚硅谷Java基础