02-Java集合之双列集合,如HashMap,Hashtable,Properties,TreeMap的底层结构

双列集合

添加/获取/删除键值对原理

哈希表/散列表是一种将数组和单向链表融合在一起的数据结构

• 数组在查询方面效率很高,单向链表在随机增删方面效率较高,哈希表将以上的两种数据结构融合在一起后充分发挥它们各自的优点

双列集合以key和value这种键值对方式存储数据: key和value都是存储对象的内存地址,其中key起到主导的地位,value是key的附属

• 集合存储键值对的key无序不可重复: 如果key重复了value会覆盖
• 集合存储键值对的key需要同时重写hashCode()+equals()方法: 先调用key的hashCode()方法确定单向链表下标,后调用key的equals()方法判断是否重复
• 集合存储键值对的vlaue需要同时重写equals()方法: 调用value的equals()方法判断是否包含某个value

双列集合添加/获取/删除元素的流程: 都是先得到对象的Hash值并转换成对应单向链表下标,然后与该单向链表上的元素进行比较

• 先调用key的hashCode方法得到一个哈希值,这个哈希值会经过哈希算法转换成对应单向链表的下标,如果该单向链表上没有元素直接存储即可
• 只有对应的单向链表上有元素时,才会调用key的equals方法与该链表中的元素进行比较
  • 添加: key重复则覆盖对应键值对的value
  • 获取: key相等则返回对应键值对的value值
  • 删除: key相等则删除对应的键值对
• 哈希碰撞: 对象返回的hash值相同转换的单向链表一定相同,但对象返回的hash值不同经过哈希算法转换的单向链表下标也可能相同

如果对象的hashCode和equals方法的返回值设置不好就会造成散列分布不均匀现象,一般使用IDEA一起生成equals+hashCode方法

• hashCode方法返回固定值: 导致底层哈希表变成了纯单向链表
• hashCode方法返回不同值: 导致底层哈希表就成为了一维数组
• 如果equals方法返回true那么hashCode方法返回值必须一样: 相同对象必须在同一个单向链表上比较,只有这样才能保证其他链表上没有该对象

重写hashCode方法

静态的内部类HashMap.Node

public class HashMap{
    // HashMap底层实际上就是一个数组（一维数组）
    Node<K,V>[] table;
    static class Node<K,V> {
        // 哈希值是调用key的hashCode()方法的执行结果,hash值会通过哈希算法转换存储成数组的下标
        final int hash; 
        // 存储到Map集合中的那个key
        final K key; 
        // 存储到Map集合中的那个value
        V value; 
        // 下一个节点的内存地址
        Node<K,V> next; 
    }
}

使用IDEA一起生成equals+hashCode方法以达到散列分布均匀的效果即每个单向链表上分布的节点个数是平均的

public class HashSetTest {
    public static void main(String[] args) {
		// 创建对象
        Student s1 = new Student("zhangsan");
        Student s2 = new Student("zhangsan");

        // 重写equals方法之后是true
        System.out.println(s1.equals(s2)); 
		// 同一个对象的hash值相同,不同对象的hash值一般不相同
        System.out.println("s1的hashCode=" + s1.hashCode()); //284720968(没重写),-1432604525(重写hashCode之后)
        System.out.println("s2的hashCode=" + s2.hashCode()); //122883338(没重写),-1432604525(重写hashCode之后)

        //s1.equals(s2)结果是true表示s1和s2是一样的,那么往HashSet集合中放的话按说只能放进去1个
        Set<Student> students = new HashSet<>();
        students.add(s1);
        students.add(s2);
        // 结果是2并不符合HashSet集合元素无序不可重复的特点
        System.out.println(students.size()); 
    }
}

// 如果equals方法返回是true，hashCode方法返回值必须相同的原则,这样才能保证在同一个单向链表中对相同元素进行比较
class Student {
    private String name;
    public Student(String name) {
        this.name = name;
    }
    //构造 + set 和 get 方法....

    // 如果学生名字一样，表示同一个学生
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        // 以下这个方法可以保证如果两个对象经过equals比较相同时,那么它们hashCode方法返回值一定相同的原则
        return Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name);
    }
}

双列集合继承结构图

超级父接口Map

常用方法

集合中元素的增删改查方法,集合中存储键值对的Key需要同时重写hashCode()+equals()方法

集合中元素的判断方法

public class MapTest01 {
    public static void main(String[] args) {
        // 创建Map集合对象
        Map<Integer, String> map = new HashMap<>();
       
        // 测试put方法,向Map集合中添加键值对
        map.put(1, "zhangsan"); // 1在这里进行了自动装箱
        map.put(2, "lisi");
        map.put(3, "wangwu");
        map.put(4, "zhaoliu");
        
        // 测试get方法,通过key获取value
        String value = map.get(2);
        System.out.println(value);
        
        // 测试方法,通过key获取value,如果key不存在则返回指定的默认值
        String value1 = map.getOrDefault()(5,"zhaoliu");// map中不存在5,则返回默认值
        System.out.println(value1);
        
        
        // 测试size方法,获取键值对的数量
        System.out.println("键值对的数量：" + map.size());
        
        // 测试remove方法,通过key删除键值对
        map.remove(2);
        System.out.println("键值对的数量：" + map.size());
        
        // 测试containsKey方法,判断是否包含某个key
        System.out.println(map.containsKey(new Integer(4))); // true
        // 判断containsValue方法,判断是否包含某个value
        System.out.println(map.containsValue(new String("wangwu"))); // true

        // 测试values方法,获取所有的value
        Collection<String> values = map.values();
        // foreach
        for(String s : values){
            System.out.println(s);
        }

        // 测试clear方法,清空map集合
        map.clear();
        System.out.println("键值对的数量：" + map.size());
        
        // 测试isEmpty()方法,判断集合是否为空
        System.out.println(map.isEmpty()); // true
    }
}

深入entrySet()方法

entrySet()方法: Map集合转换成的Set集合中的元素的类型是Map.Entry<K,V>类型

  # Map集合存储对象
  key             value
  ----------------------------
  1               zhangsan
  2               lisi
  3               wangwu
  4               zhaoliu

  #Set集合存储对象,集合中元素的类型是Map.Entry类型
  1=zhangsan
  2=lisi     
  3=wangwu
  4=zhaoliu

Map.Entry和String一样都是一种类型的名字,只不过Map.Entry是Map中静态内部类,并且这个类声明的时候指定了泛型

public class MyMap {
    // 声明一个静态内部类并且指定了泛型, 类名叫做：MyMap.MyEntry<K,V>
    public static class MyEntry<K,V> {
        // 内部类中的静态方法
        public static void m1(){
            System.out.println("静态内部类的m1方法执行");
        }

        // 内部类中的实例方法
        public void m2(){
            System.out.println("静态内部类中的实例方法执行！");
        }

    }
    
    public static void main(String[] args) {
        // 执行内部类中的静态方法
     	MyMap.MyEntry.m1();

        // 创建静态内部类对象,执行内部类中的实例方法
      	MyMap.MyEntry mm =  new MyMap.MyEntry()
        mm.m2();
        
        // 声明一个Set集合,存储的对象类型是String类型
        Set<String> set2 = new HashSet<>();

        // 声明一个Set集合,存储的对象是MyMap.MyEntry类型,没有指定泛型默认是Object类型
        Set<MyMap.MyEntry> set = new HashSet<>();

		// 声明一个Set集合,存储的对象是MyMap.MyEntry<Integer, String>类型
        Set<MyMap.MyEntry<Integer, String>> set3 = new HashSet<>();
    }
}

Map集合的遍历

第一种: 调用Map集合的keySet()方法获取存储集合所有key的Set集合,使用迭代器或者foreach的方式遍历Set集合中的每一个key并通过key获取value

// 向Map集合中添加元素
Map<Integer, String> map = new HashMap<>();
map.put(1, "zhangsan");
map.put(2, "lisi");

// 获取所有的key,所有的key存储在一个Set集合
Set<Integer> keys = map.keySet();

// 使用迭代器的方式遍历keys集合,通过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的方式遍历key,通过key获取value
for(Integer key : keys){
    System.out.println(key + "=" + map.get(key));
}

第二种(推荐): 调用Map集合的entrySet()方法直接把Map集合转换成Set集合,遍历Set集合中的每一个节点对象,通过节点对象的方法获取key和value

// 向Map集合中添加元素
Map<Integer, String> map = new HashMap<>();
map.put(1, "zhangsan");
map.put(2, "lisi");

// 把Map集合转换成Set集合,Set集合中元素的类型是Map.Entry
Set<Map.Entry<Integer,String>> set = map.entrySet();

// 使用迭代器的方式遍历Set集合,集合中存储的Node对象有Key和Value属性
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);
}

// 使用foreach的方式遍历Set集合
for(Map.Entry<Integer,String> node : set){
    System.out.println(node.getKey() + "--->" + node.getValue());
}

Map接口实现类

HashMap集合(哈希表)

HashMap底层实际上就是个一维数组,这个数组中每一个元素是一个单向链表,集合中存储键值对的key无序不可重复

• 无序: 添加的键值对不一定挂到哪个单向链表上
• 不可重复: 先调用key的hashCode方法确定单向链表下标,后调用key的equals方法判断是否相等, 如果key重复了value会覆盖
• key和value允许为null: 调用key的hashCode方法或者value的equals方法时如果为null会做判断,集合的key允许为null但只能有一个(key重复value还是会覆盖)
• 安全: 线程不安全

HashMap集合的默认初始化容量是16, 默认加载因子是0.75

• 初始化容量必须是2的倍数,便于实现散列均匀的效果,从而提高HashMap集合的存取效率
• 当HashMap集合底层数组的容量达到75%的时候数组按照2的倍数开始扩容

public class HashMapTest01 {
    public static void main(String[] args) {
        // Integer是key，它的hashCode和equals都重写了
        Map<Integer,String> map1 = new HashMap<>();
        map.put(1111, "zhangsan");
        map.put(2222, "zhaoliu");
        map.put(2222, "king"); //key重复的时候value会自动覆盖

        System.out.println(map.size()); // 2

        // 遍历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());
        }
        
        Map map2 = new HashMap();
        // HashMap集合允许key为null
        map2.put(null, null);
        System.out.println(map2.size()); // 1

        // key重复的话value会覆盖
        map2.put(null, 100);
        System.out.println(map2.size()); //1

        // 通过key获取value
        System.out.println(map2.get(null)); // 100  
    }
}

Hashtable集合(哈希表)

Hashtable底层是哈希表数据结构,默认初始化容量是11,默认加载因子是0.75

• 当HashMap集合底层数组的容量达到75%的时候数组按照原容量*2 + 1的机制开始扩容

• key和value不能为null: 因为其在添加/获取/删除元素时首先就会调用key的hashCode方法或者value的equals方法

• 安全: 线程安全即类中的方法都带有synchronized关键字,但其对线程的处理导致效率较低,一般使用currentHashMap代替

public class HashtableTest01 {
    public static void main(String[] args) {
        Map map = new Hashtable();
        //map.put(null, "123");
        map.put(100, null);

    }
}

Properties集合(哈希表)

Properties是Hashtable的子类,底层是哈希表数据结构且是线程是安全的,key和value只能存储String类型的字符串

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.mysql.jdbc.Driver");
        pro.setProperty("username", "root");
        pro.setProperty("password", "123");

        // 通过key获取value
        String url = pro.getProperty("url");
        String driver = pro.getProperty("driver");
        String username = pro.getProperty("username");
        String password = pro.getProperty("password");

        System.out.println(url);
        System.out.println(driver);
        System.out.println(username);
        System.out.println(password);

    }
}

TreeMap(自平衡二叉树)

由于TreeMap集合实现了SortedSet接口,所以集合中存储的键值对的key默认按照字典顺序规则升序排序,也可以通过两种方式手动指定排序规则

• 第一种方式: 存储的键值对的key需实现Comparable接口,然后重写compareTo方法(返回值决定了元素的排序规则),key重写了该方法后就无需重写equals方法
• 第二种方式: 构造TreeMap集合时传入一个实现了Comparator接口的比较器对象并重写了compare方法,该比较器对象可以对集合中的元素进行挨个比较

String和Integer以及Date类底层都实现了Comparable接口

Comparable可比较接口和Comparator比较器接口的应用特点

• Comparable接口: 适用于比较规则不会发生改变的时候,或者比较规则只有1个的时候
• Comparator接口: 适用于比较规则之间需要频繁切换,或者比较规则有多个的时候

存储到集合中键值对的key实现Comparable接口并重写compareTo(返回值决定了元素的排序规则)方法,这样集合中的元素就会按照我们指定的规则排序

• 存储键值对时会先调用key1的compareTo(key2) 方法,返回0表示元素的key相同即覆盖(代替equals方法),不等于0表示按照从大到小或者从小到大顺序排序

public class TreeSetTest05 {
    public static void main(String[] args) {
        TreeMap<Vip> vips = new TreeMap<>();
        vips.add(new Vip("zhangsi", 20));
        vips.add(new Vip("zhangsan", 20));
        vips.add(new Vip("king", 18));
        vips.add(new Vip("soft", 17));
        for(Vip vip : vips){
            System.out.println(vip);
        }
    }
}
// 存储到集合中键值对的key需要实现Comparable接口
class Vip implements Comparable<Vip>{
    String name;
    int age;
    public Vip(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "Vip{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    // 在compareTo方法中编写比较的规则,方法的返回值决定了排序的顺序
    @Override
    public int compareTo(Vip v) {
       // 年龄相同时按照名字排序
        if(this.age == v.age){
            // String类型实现了Comparable接口，可以直接调用compareTo方法来完成比较
            return this.name.compareTo(v.name);
        } else {
            // 年龄不一样按照年龄排序
            return this.age - v.age;
        }
    }
}

构造TreeMap集合时传入一个实现了Comparator接口的比较器对象并重写了compare方法,该对象可以对集合中的元素进行挨个比较

• 创建Comparator接口的实现类对象时可以使用匿名内部类的方式,也可以单独定义一个类继承Comparator接口后再创建对象

public class TreeSetTest06 {
    public static void main(String[] args) {
        // 使用匿名内部类的方式创建比较器对象,也可以单独在这里编写一个类实现Comparator接口
        TreeSet<WuGui> wuGuis = new TreeSet<>(new Comparator<WuGui>() {
            @Override
            public int compare(WuGui o1, WuGui o2) {
                return o1.age - o2.age;
            }
        });

        wuGuis.add(new WuGui(1000));
        wuGuis.add(new WuGui(800));
        wuGuis.add(new WuGui(810));

        for(WuGui wuGui : wuGuis){
            System.out.println(wuGui);
        }
    }
}

// 乌龟
class WuGui{
    int age;
    public WuGui(int age){
        this.age = age;
    }
    @Override
    public String toString() {
        return "小乌龟[" +
                "age=" + age +
                ']';
    }
}

// 单独定义一个类继承Comparator接口
class WuGuiComparator implements Comparator<WuGui> {
    @Override
    public int compare(WuGui o1, WuGui o2) {
        // 按照年龄排序
        return o1.age - o2.age;
    }
}