java中集合(Map部分)

集合的继承结构

要点

集合在java中是一个容器，一个对象。集合不能直接存储基本数据类型，也不能直接存储java对象，
集合当中存储的都是java对象的内存地址（引用）
    list.add(100);//100自动装箱成Integer类型

java中每一个不同的集合底层对应不同的数据结构，往不同集合中存储元素就是将数据放到了不同的数据结构中。
数据结构是数据存储的结构，不同数据结构，数据存储方式不同。
java已经将常见的数据结构实现了封装成集合类，我们只需要学会怎么调用集合类即可

在java中集合分为两大类:
一类是单个方式存储元素:
    这一类集合中超级父接口:java.util.Collection;
一类是以键值对的方式存储元素
    这一类集合中超级父接口:java.util.Map;
Collection集合和Map集合没有关系，二者独立存在。

Collection继承结构图(常用部分)

Map继承结构图(常用部分)：

Map接口中常用方法

要点

java.util.Map接口特点和常用方法:

    1、Map和Collection没有继承关系。
    2、Map集合以key和value的方式存储数据:键值对
        key和value都是引用数据类型，都是存储对象的内存地址。
        key起到主导的地位，value是key的一个附属品。

    3、Map接口中常用方法:

        V put(K key, V value)   向Map集合中添加键值对
        V get(Object key)   通过key获取value
        void clear()    清空vap集合
        boolean containsKey(Object key) 判断Map中是否包含某个key
        boolean containsValue(Object value) 判断Map中是否包含某个value
            containsKey和containsValue方法在底层调用equals方法进行比对判断集合中是否包含某个元素。

        boolean isEmpty()   判断Map集合中元素个数是否为空
        V remove(Object key)    通过key删除键值对
            remove方法在底层调用equals方法进行比对判断集合中是否包含某个元素。

        int size()  获取Map集合中键值对的个数。
        Collection<V> values()  获取Map集合中所有的值并返回一个Collection
        Set<K> keySet() 获取Map集合所有的key (所有的键是一个set集合)
        Set<Map.Entry<K,V>> entrySet()  将Map集合转换成Set集合
        
        eg：假设现在有一个Map集合，如下所示:
            map1集合对象
            key           value
            1             zhangsan
            2             lisi
            3             wangwu
            4             zhaoliu

            Set set = map1.entrySet();

            set集合对象：
            1=zhangsan
            2=lisi
            3=wangwu
            4=zhaoliu --->这个东西是个什么? Map.Entry类型的对象

            注意:Map集合通过entrySet()方法转换成的这个Set集合，Set集合中元素的类型是Map.Entry<K,V>,
                Map.Entry和String一样，都是一种类型的名字，只不过Map.Entry是Map中的静态内部类

Map.Entry源码：

Map集合的遍历(重要！！！)

public class MapTest{
public static void main(String[] args) {

//第一种方式:获取所有的key，通过遍历key ，来遍历value
Map<Integer,String> map = new HashMap<>();
map.put(1,"zhangsan");
map.put(2,"lisi");
map.put(3,"wangwu");
map.put(4,"zhaoliu" );

//遍历Map集合

//第一种方式：获取所有的key,通过key获取value
//所有的key是一个Set集合
Set<Integer> keys = map.keySet();
//遍历key ，通过key获取value
//迭代器可以
/*  Iterator<Integer> it = keys.iterator();
    while(it.hasNext()){
    //取出其中一个key
    Integer key = it.next();//通过key获取value
    String value = map.get(key );  
    System.out.println(key + "=" + value);
}*/
//foreach也可以
for(Integer key : keys){
    System.out.println(key+"="+map.get(key));
}

//第二种方式: Set<Map.Entry<K,V>> entrySet()
//把Map集合直接全部转换成Set集合,Set集合中元素的类型是:Map.Entry
Set<Map.Entry<Integer,String>> set = map.entrySet( );
//遍历Set集合，每一次取出一个Node
//迭代器
/*
Iterator<Map.Entry<Integer,String>> it2 = set.iterator();
while(it2.hasNext()){
    Map.Entry<Integer,String> node = it2.next( );
    Integer key = node.getKey( );
    String value = node.getVaLue( );
    System.out.println(key + "=" + value);
}
*/
 
//这种方式效率比较高，因为获取key和value都是直接从node对象中获取的属性值。
//这种方式比较适合于大数据量
for(Map.Entry<Integer,String> node : set){
    System.out.println(node.getKey() + "--->" + node.getvalue());
    }
}
}

HashMap

要点

HashMap集合：
1、HashMap集合底层是哈希表/散列表的数据结构，是非线程安全的。
2、哈希表是―个怎样的数据结构呢?
    哈希表是一个数组和单向链表的结合体。
    数组∶在查询方面效率很高，随机增删方面效率很低。
    单向链表:在随机增删方面效率较高，在查询方面效率很低。
    哈希表将以上的两种数据结构融合在一起，充分发挥它们各自的优点。
3、 HashMap集合底层的源代码:
    public class HashMap{
        //HashMap底层实际上就是一个数组。(一维数组)
        Node<K,V>[] table;
        //静态的内部类HashMap.Node
        static class Node<K,V>{
            final int hash;//哈希值（哈希值是key的hashCode()方法的执行结果。hash值通过哈希函数/算法得到数组下标
            final K key;//存储到Map集合中的那个key
            V value;//存储到Map集合中的那个value
            Node<K,V> next; //下一个节点的内存地址。
        }
    }
    哈希表/散列表︰一维数组，这个数组中每一个元素是一个单向链表。（数组和链表的结合体。)

4、最主要掌握的是:
    map.put(k,v)
    v=map.get(k)
    以上这两个方法的实现原理，是必须掌握的。

    1）map.put(k,v)实现原理:
    第一步:先将k、v封装到Node对象当中。
    第二步∶底层会调用k的hashCode()方法得出hash值，
    然后通过哈希函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。
    如果说下标对应的位置上有链表，此时会拿着k和链表上每一个节点中的k进行equals比较，
        如果所有的equals方法返回都是false，那么这个新节点将会被添加到链表的末尾。
        如果其中有一个equals返回了true，那么这个节点的value将会被覆盖。
    
    重点:HashMap集合的key,会先后调用hashCode()和equals()两个方法（数组下标位置上如果没有任何元素就不用调用equals方法）,
    这两个方法都需要重写。hashCode()和equals()两个方法直接idea同时生成。
    
    2）v = map.get(k)实现原理∶
    先调用k的hashCode方法得出哈希值，通过哈希算法转换成数组下标，通过数组下标快速定位到某个位置上，
    如果这个位置上什么也没有，返回null。
    如果这个位置上有单向链表，那么会拿着参数k和单向链表上的每个节点中的k进行equals比较 ，
        如果所有equals方法返回false，那么get方法返回null，只要其中有一个节点的k和参数k equals的时候返回true，
        那么此时这个节点的value就是我们要找的value，get方法最终返回这个要找的value。

5、为什么哈希表的随机增删,以及查询效率都很高?
        增删是在链表上完成。
        查询也不需要都扫描，只需要部分扫描。
    
6、HashMap集合的key部分特点:
    无序，不可重复。key值可以为null，但是null值只能有一个。
    为什么无序?因为根据hash算法得到的数组下标决定挂到哪个单向链表上，该顺序不是线性顺序。
    不可重复是怎么保证的? equals方法保证HashMap集合的key不重复。如果key重复了, value会覆盖。

    放在HashMap集合key部分的元素其实就是放到HashSet集合中了。
    所以HashSet集合中的元素也需要重写hashCode()和equals()方法。

7、哈希表HashMap使用不当时无法发挥性能!
    注意:同一个单向链表上所有节点的hash值可以不同，但他们经过hashCode方法算出的的数组下标是一样的（哈希碰撞）。
    但同一个链表上k和k的equals方法肯定返回的是false,都不相等。

    假设将所有的hashCode()方法返回值固定为某个值,那么会导致底层哈希表变成了纯单向链表。
    这种情况我们成为:散列分布不均匀。
    
    假设将所有的hashCode()方法返回值都设定为不一样的值会导致底层哈希表就成为一维数组了，没有链表的概念了。
    也是散列分布不均匀。

    什么是散列分布均匀?
        假设有100个元素, 10个单向链表，那么每个单向链表上有10个节点,这是最好的,是散列分布均匀的。
        
    散列分布均匀需要你重写hashCode()方法时有一定的技巧。
        
8、HashMap集合的默认初始化容量是16，默认加载因子是0.75
    这个默认加载因子是当HashMap集合底层数组的容量达到75%的时候,数组开始扩容，扩容之后的容量是原容量的2倍。

    重点，记住: HashMap集合初始化容量必须是2的倍数,这也是官方推荐的，
    这样有助于达到散列均匀，提高HashMap集合的存取效率。

    在JDK8之后，如果哈希表单向链表中元素超过8个，单向链表会变成红黑树结构，
    当红黑树上的结点数量小于6时，会重新把红黑树变成单向链表。这样缩小扫描范围，提高检索效率。

HashMap中Node的结构：



HashMap中Node的源码：

实例

public class HashMapTest01 {
    public static void main(String[] args) {
        //测试HashMap集合key部分的元素特点
        // Integer是key，Integer的hashCode和equals方法官方都重写了。
        // String是value，String的hashCode和equals方法官方都重写了。
        Map<Integer,String> map = new HashMap<>();
        map.put(1111,"zhangsan");
        map.put(6666,"lisi");
        map.put(7777,"wangwu");
        map.put (2222,"zhaoliu");
        map.put(2222,"king"); //key 重复的时候value会自动覆盖。
        System.out.println(map.size()); // 4

        //遍历Map集合
        Set<Map.Entry<Integer, String>>set = map.entrySet();
        for(Map.Entry<Integer,String> entry:set){
            //验证结果:HashMap集合key部分元素:无序不可重复。
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }
    }

关于ConcurrentHashMap：

Hashtable

要点

Hashtable的key可以为null吗?
Hashtable的key和value都是不能为null的。HashMap集合的key和value都是可以为null的。

Hashtable方法部带有synchronized是线程安全的。线程安全有其它的方案，这个Hashtable对线程的处理导致效率较低，使用较少了。
Hashtable和HashMap一样，底层都是哈希表数据结构。
Hashtable的初始化容量是11，默认加载因子是:0.75f。Hashtable的扩容是:原容量*2 +1。
   
Properties是一个Map集合，继承Hashtable，Properties的key和value都是String类型。
Properties被称为属性类对象，是线程安全的，用得较多。
Properties中的两个方法：
setProperty(String,String)  存Properties对象，底层调用Hashtable的put(key,value)方法。
getProperty(key)    通过键取Properties对象的值

Properties

public class PropertiesTest01 {
    public static void main(String[] args) {
        //创建一个Properties对象
        Properties pro = new Properties();

        //需要掌握Properties的两个方法，一个存，一个取。
        pro.setProperty("url", "jdbc :mysql://localhost:3306/bjpowernode");
        pro.setProperty("driver" , " com.mysq1.jdbc.Driver" );
        pro.setProperty ("username" , "root");
        pro.setProperty("password" , "123");

        //通过key获取value
        String url = pro.getProperty( "ur1");
        String driver = pro.getProperty("driver" );
        String username = pro.getProperty( "username") ;
        String password = pro.getProperty( "password");
        System.out.print1n(url );
        System.out.println(driver);
        System.out.println(username);
        System.out.println(password);
    }
}   

SortedMap

TreeSet

要点

1、TreeSet集合底层实际上是一个TreeMap,TreeMap集合底层是一个自平衡二叉树，遵循左小右大原则存放。
2、到TreeSet集合中的元素，等同于放到TreeMap集合key部分了。
3、TreeSet集合中的元素:无序不可重复，但是可以按照元素的大小顺序自动排序，放的时候按顺序放，取得时候顺序取。称为:可排序集合。
    TreeSet集合、TreeMap集合、Iterator迭代器采用的是中序遍历方式。

4、对自定义的类型来说，TreeSet可以排序吗?
自定义类没有实现java.lang.Comparable接口，没有指定自定义类型对象之间的比较规则，
TreeSet无法对自定义类型对象排序，但是程序员可以通过两种方法指定比较规则：
    ① 实现java.lang.Comparable接口(实现compareTo方法。)
    ② 单独编写java.util.Comparator比较器。
    当比较规则不会发生变化或比较规则只有一个的时，建议实现Comparable接口
    当比较规则有多个并且需要多个比较规则之间频繁切换时，建议使用Comparator接口

Integer和String类默认实现了Comparable接口，TreeSet可以对Integer和String进行排序并存储。

以下实例一程序运行的时候出现了这个异常:
Exception in thread "main" java.lang.ClassCastException: 
Person cannot be cast to java.lang.Comparable
出现这个异常的原因是：
    Person类没有实现java.lang.Comparable接口，没有指定Person类对象之间的比较规则

实例一

public class TreeSetTest01{
public static void main(String[] args) {
    //创建一个TreeSet集合
    TreeSet<String> ts = new TreeSet<>();//添加String
    ts.add("zhangsan");
    ts.add("lisi");
    ts.add("wangwu");
    ts.add("zhangsi");
    ts.add("wangliu");

    for(String s : ts){
    //按照字典顺序，升序
        System.out.println(s);
    }

    TreeSet<Integer> ts2 = new TreeSet<>();
    ts2.add(100);
    ts2.add(200);
    ts2.add(90);
    ts2.add(800);
    ts2.add(600);
    ts2.add(10);

    for(Integer elt : ts2){
        //升序输出
        System.out.println(elt);
    }

    Person p1=new Person(32);
    Person p2=new Person(20);
    Person p3=new Person(30);
    Person p4=new Person(25);

    TreeSet<Person> persons=new TreeSet<>();

    persons.add(p1);
    //没有指定Person类型对象之间的排序规则，比完才知道怎么排序，p2对象无法加入persons
    //报错：java.lang.ClassCastException: Person cannot be cast to class java.lang.Comparable
    persons.add(p2);
 
}

}
class Person{
int age;
public Person(int age){
this.age=age;
}

实例二

public class TreeSetTest02 {
public static void main(String[] args) {
    Person p1=new Person(32);
    Person p2=new Person(20);
    Person p3=new Person(30);
    Person p4=new Person(25);

    TreeSet<Person> persons=new TreeSet<>();

    persons.add(p1);
    persons.add(p2);
    persons.add(p3);
    persons.add(p4);
    for (Person p:persons){
        System.out.println(p);
    }
}
}
class Person implements  Comparable<Person>{
    int age;
    public  Person(int age){
        this.age=age;
    }
    //实现Comparable接口中的compareTo方法，编写比较规则
    //k.compareTo(t.key)
    //拿着参数k和集合中的每一个k进行比较，返回值可能是>0 <0 =0
    //比较规则最终还由程序员指定的
    //按照年龄降序排序
    public  int compareTo(Person p){//p1.compareTo(p2)
        return p.age -  this.age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                '}';
    }
}

实例三

public class TreeMapTest03 {
public static void main(String[] args) {
    //TreeSet<Animal> animals=new TreeSet<>();///这样不行没有通过构造方法传一个比较器进去。
    //创建TreeSet集合时需要使用比较器，给构造方法传一个比较器
    //TreeSet<Animal> animals = new TreeSet<>(new AnimalComparator());

    //可以使用匿名内部类的方式,直接new Comparoter接口并实现
    TreeSet<Animal> animals = new TreeSet<>(new Comparator<Animal>(){
        @Override
        public int compare(Animal o1, Animal o2) {
            return o1.age - o2.age;
        }
    });
    animals.add(new Animal(300));
    animals.add(new Animal(50));
    animals.add(new Animal(100));

    for (Animal animal:animals){
        System.out.println(animal);
    }
}
}
class Animal{
    int age;
    public  Animal(int age){
        this.age=age;
    }

    @Override
    public String toString() {
        return "Animal{" +
                "age=" + age +
                '}';
    }
    }
/*
//单独编写一个比较器，实现java.util.Comparator接口
//Comparator是java.util包下的，Comparable是java.lang包下的
class AnimalComparator implements  Comparator<Animal>{
    @Override
    public int compare(Animal o1, Animal o2) {
        //指定比较规则
        return o1.age-o2.age;
    }
}
*/

Collections

要点

Collections是一个集合工具类，提供线程安全、排序等多个方法方便集合操作。
Collections在java.util包下，与java.lang.Collection 没有继承关系。

实例

public class CollectionsTest {
    public static void main(String[] args) {
        //ArrayList集合不是线程安全
        List<String> list=new ArrayList<>();

        //将ArrayList变成线程安全的
        Collections.synchronizedList(list);

        //排序
        list.add("abf");
        list.add("abx");
        list.add("abc");

        Collections.sort(list);
        for (String s:list)
            System.out.println(s);

        List<Animal2> animals = new ArrayList<>();
        animals.add(new Animal2(10));
        animals.add(new Animal2(20));
        animals.add((new Animal2(30)));
        //注意：对list集合中元素排序需要实现Comparable接口
        Collections.sort(animals);
        for (Animal2 a:animals){
            System.out.println(a);
        }

        //对Set集合排序
        Set<String > set=new HashSet<>();
        set.add("king");
        set.add("kingsort");
        set.add("king2");

        //将Set集合转换成List集合
        List<String> myList=new ArrayList<>(set);
        Collections.sort(myList);
    }
    //Collections.sort(list集合，比较器对象);也可以对list排序
}
class  Animal2 implements  Comparable<Animal2>{
    int age;

    public Animal2(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Animal2{" +
                "age=" + age +
                '}';
    }

    @Override
    public int compareTo(Animal2 o) {
        return this.age-o.age;
    }
}