day16.Map集合

  1. 课前回顾:
  2.     1.LinkedList:
  3.       特点:有序  元素可重复  有索引
  4.       数据结构:双向链表
  5.       方法:有很多直接操作首尾元素的方法
  6.     2.增强for:遍历集合或者数组->foreach
  7.       格式:
  8.        for(元素类型 变量名:集合名或者数组名){
  9.            变量名就代表的是每一个元素
  10.        }
  11.       注意:
  12.        使用增强for的时候,不要随意改变集合长度
  13.        当用增强for遍历集合时,实现原理是迭代器
  14.        当用增强for遍历数组时,实现原理就是普通的for
  15.     3.集合工具类:Collections
  16.       方法:
  17.        shuffle(集合)->打乱元素顺序
  18.        sort(集合)->排序
  19.        sort(集合,比较器)->按照指定的规则排序
  20.     4.比较器:
  21.       Comparable
  22.       Comparator
  23.     5.泛型:
  24.       定义类:  public class 类名<E>{}
  25.       定义方法:  修饰符 <E> 返回值类型 方法名(E e){}
  26.       定义接口:  public interface 接口名<E>{}
  27.     6.Set接口
  28.       Set接口中的方法没有对Collection中的方法进行扩充
  29.     7.HashSet
  30.       特点:
  31.         无序
  32.         无索引
  33.         元素不可重复
  34.       数据结构:哈希表
  35.               jdk8之前:哈希表 = 数组+链表
  36.               jdk8之后:哈希表 = 数组+链表+红黑树
  37.               加入红黑树原因:查找快
  38.        方法:底层都是依靠HashMap实现的
  39.      8.LinkedHashSet:
  40.        特点:
  41.         有序
  42.         无索引
  43.         元素不可重复
  44.        数据结构:链表+哈希表
  45.      9.哈希值:需要调用hashCode方法计算出来的一个十进制数
  46.              内容不一样,哈希值有可能一样
  47.              内容一样,哈希值一定一样的
  49.      10.HashSet存储元素的过程(和今天要学的HashMap是一样的)
  50.         先比较元素的哈希值,再比较元素的内容
  51.         如果哈希值不一样,直接存
  52.         如果哈希值一样,再比较内容
  53.         如果内容不一样,也存
  54.         如果内容一样,哈希值也一样,后面的把前面的覆盖掉
  55.      11.注意:存储的时候比较的哈希值(是内容的哈希值)  内容(就是内容)
  56.             所以,存储到set集合中保证元素唯一的话,需要重写hashCode和equals方法
  58.  今日重点:
  59.     1.Map的全部
  60.     2.知道HashMap和HashTable的区别
  61.     3.会使用Properties集合
  62.     4.会集合嵌套
  63.     5.了解哈希表的存储过程和细节
  64.     6.会操作TreeSet和TreeMap

第一章.Map集合

day16[Map集合] - 图1

1.Map的介绍

  1. 1.概述:
  2.    双列集合的接口
  3. 2.特点:
  4.    元素都是key value形式(键值对)存储  ->一个key 对应一个value
  5.    key唯一  (将key去重复,过程和HashSet一样)
  6.    无序
  7.    没有索引
  8. 3.元素形式:
  9.   map.put("文章","马伊琍")
  10.   map.put("文章","姚笛")->和上面的key重复,会将上面的键值对覆盖

2.HashMap的介绍以及使用

  1. 1.HashMap 实现了 Map接口
  2. 2.特点:
  3.    元素都是key value形式(键值对)存储  ->一个key 对应一个value
  4.    key唯一  (将key去重复,过程和HashSet一样)
  5.    无序
  6.    没有索引
  7. 3.数据结构:哈希表
  8.           jdk8之前:哈希表 = 数组+链表
  9.           jdk8之后:哈希表 = 数组+链表+红黑树
  10. 4.方法:
  11. - public V put(K key, V value):  把指定的键与指定的值添加到Map集合中。
  12. - public V remove(Object key): 把指定的键 所对应的键值对元素 在Map集合中删除，返回被删除元素的值。
  13. - public V get(Object key) 根据指定的键，在Map集合中获取对应的值。
  14. - public Set<K> keySet(): 获取Map集合中所有的键，存储到Set集合中。
  15. - public Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)。
  16. - public boolean containsKey(Object key):判断该集合中是否有此键。
  17. - public Collection<V> values() 返回Map集合中的所有值到Collection集合。
  1. public class Test01 {
  2.     public static void main(String[] args) {
  3.         //创建HashMap集合
  4.         HashMap<String, String> hashMap = new HashMap<>();
  5.         //- public V put(K key, V value):  把指定的键与指定的值添加到Map集合中。
  6.         hashMap.put("郭靖","黄蓉");
  7.         hashMap.put("杨过","小龙女");
  8.         hashMap.put("张无忌","赵敏");
  9.         hashMap.put("张翠山","殷素素");
  10.         hashMap.put("张无忌","周芷若");
  11.         System.out.println(hashMap);
  12.         //- public V remove(Object key): 把指定的键 所对应的键值对元素 在Map集合中删除，返回被删除元素的值。
  13.        /* String value1 = hashMap.remove("郭靖");
  14.         System.out.println(value1);
  15.         System.out.println(hashMap);*/
  16.         //- public V get(Object key) 根据指定的键，在Map集合中获取对应的值。
  17.         String value2 = hashMap.get("杨过");
  18.         System.out.println(value2);
  20.         //- public boolean containsKey(Object key):判断该集合中是否有此键。
  22.         boolean result01 = hashMap.containsKey("杨过");
  23.         System.out.println(result01);
  24.         //- public Collection<V> values() 返回Map集合中的所有值到Collection集合。
  25.         Collection<String> collection = hashMap.values();
  26.         System.out.println(collection);
  27.     }
  28. }

3.HashMap的两种遍历方式

3.1方式一:获取key,然后根据key获取值

  1. - public Set<K> keySet(): 获取Map集合中所有的键，存储到Set集合中。
  1. public class Test02 {
  2.     public static void main(String[] args) {
  3.         HashMap<String, String> hashMap = new HashMap<>();
  4.         hashMap.put("郭靖","黄蓉");
  5.         hashMap.put("杨过","小龙女");
  6.         hashMap.put("张无忌","赵敏");
  7.         hashMap.put("张翠山","殷素素");
  8.         hashMap.put("涛哥","柳岩");
  10.         /*
  11.           将map中的所有key获取出来,存到set集合中
  12.          */
  13.         Set<String> set = hashMap.keySet();
  15.         /*
  16.           遍历set集合,将key都遍历出来
  17.           然后调用map中的get(key)->根据key获取对应的value
  18.          */
  19.         for (String key : set) {
  20.             String value = hashMap.get(key);
  21.             System.out.println(key+"..."+value);
  22.         }
  23.     }
  24. }

3.2方式二:同时获取key和value

day16[Map集合] - 图2

  1. - public Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象,放到set集合中(Set集合)。
  1. public class Test03 {
  2.     public static void main(String[] args) {
  3.         HashMap<String, String> hashMap = new HashMap<>();
  4.         hashMap.put("郭靖","黄蓉");
  5.         hashMap.put("杨过","小龙女");
  6.         hashMap.put("张无忌","赵敏");
  7.         hashMap.put("张翠山","殷素素");
  8.         hashMap.put("涛哥","柳岩");
  10.        /*
  11.          将记录着键值对的Map.Entry对象获取出来,放到set集合中
  12.         */
  13.         Set<Map.Entry<String, String>> set = hashMap.entrySet();
  15.         /*
  16.           将Map.Entry从set中遍历出来
  17.           遍历出来之后,就可以用getKey  getValue
  18.          */
  19.         for (Map.Entry<String, String> entry : set) {
  20.             String key = entry.getKey();
  21.             String value = entry.getValue();
  22.             System.out.println(key+"="+value);
  23.         }
  24.     }
  25. }

5.HashMap存储自定义对象

  1. 1.如何保证key唯一呢?
  2.   重写hashCode和equals方法
  1. public class Person {
  2.     private String name;
  3.     private int age;
  5.     public Person() {
  6.     }
  8.     public Person(String name, int age) {
  9.         this.name = name;
  10.         this.age = age;
  11.     }
  13.     public String getName() {
  14.         return name;
  15.     }
  17.     public void setName(String name) {
  18.         this.name = name;
  19.     }
  21.     public int getAge() {
  22.         return age;
  23.     }
  25.     public void setAge(int age) {
  26.         this.age = age;
  27.     }
  29.     @Override
  30.     public String toString() {
  31.         return "Person{" +
  32.                 "name='" + name + '\'' +
  33.                 ", age=" + age +
  34.                 '}';
  35.     }
  37.     @Override
  38.     public boolean equals(Object o) {
  39.         if (this == o) return true;
  40.         if (o == null || getClass() != o.getClass()) return false;
  41.         Person person = (Person) o;
  42.         return age == person.age &&
  43.                 Objects.equals(name, person.name);
  44.     }
  46.     @Override
  47.     public int hashCode() {
  48.         return Objects.hash(name, age);
  49.     }
  50. }
  1. public class Test04 {
  2.     public static void main(String[] args) {
  3.         HashMap<Person, String> hashMap = new HashMap<>();
  4.         hashMap.put(new Person("涛哥",18),"廊坊");
  5.         hashMap.put(new Person("柳岩",36),"湖南");
  6.         hashMap.put(new Person("涛哥",18),"北京");
  7.         System.out.println(hashMap);
  8.     }
  9. }

6.Map的练习

  1. 需求:利用HashMap集合统计字符串中字符出现的次数
  2. 步骤:
  3. 1.创建HashMap集合  key为String   value为Integer
  4.    key代表字符   value代表字符在字符串中出现的次数
  6. 2.遍历字符串,将每一个字符都获取出来
  8. 3.在遍历的过程中,拿着字符去判断,判断map集合中是否包含遍历出来的字符
  10. 4.如果不包含,直接将字符存进去,value存为1
  12. 5.如果包含,将字符对应的value获取出来,对value进行加1,再将字符和加完之后的value重新存到map中
  14. 6.输出

day16[Map集合] - 图3

  1. public class Test05 {
  2.     public static void main(String[] args) {
  3.         /*1.创建HashMap集合  key为String   value为Integer
  4.         key代表字符   value代表字符在字符串中出现的次数*/
  5.         HashMap<String, Integer> hashMap = new HashMap<>();
  7.         //2.遍历字符串,将每一个字符都获取出来
  8.         Scanner sc = new Scanner(System.in);
  9.         System.out.println("请你输入一个字符串:");
  10.         String data = sc.next();
  11.         char[] chars = data.toCharArray();
  12.         for (char aChar : chars) {
  13.             String key = aChar+"";
  14.          //3.在遍历的过程中,拿着字符去判断,判断map集合中是否包含遍历出来的字符
  15.           if (!hashMap.containsKey(key)){
  16.               //4.如果不包含,直接将字符存进去,value存为1
  17.               hashMap.put(key,1);
  18.           }else{
  19.               //5.如果包含,将字符对应的value获取出来,对value进行加1,再将字符和加完之后的value重新存到map中
  20.               Integer value = hashMap.get(key);
  21.               value++;
  22.               hashMap.put(key,value);
  23.           }
  25.         }
  26.         //6.输出
  27.         System.out.println(hashMap);
  28.     }
  29. }

7.LinkedHashMap

  1. 1.概述:  LinkedHashMap 是 HashMap的子类
  2. 2.特点:
  3.   key唯一
  4.   无索引
  5.   有序
  6. 3.数据结构:
  7.   链表+哈希表
  8. 4.其他的方面和HashMap一模一样
  1. public class Test06 {
  2.     public static void main(String[] args) {
  3.         LinkedHashMap<String, String> map = new LinkedHashMap<>();
  4.         map.put("张无忌","赵敏");
  5.         map.put("张学良","于凤至");
  6.         map.put("张翠山","殷素素");
  7.         map.put("杨逍","纪晓芙");
  8.         System.out.println(map);
  9.     }
  10. }

第二章.TreeSet

  1. 1.概述: 是Set接口的实现类
  2. 2.特点:
  3.   无索引
  4.   元素唯一
  5.   对元素进行排序
  6. 3.数据结构:基于红黑树实现的
  7. 4.构造:
  8.   TreeSet() -> 对元素进行自然排序
  9.   TreeSet(Comparator<? super E> comparator) -> 利用比较器对元素指定排序规则
  1. public class Demo01TreeSet {
  2.     public static void main(String[] args) {
  3.         TreeSet<String> treeSet = new TreeSet<>();
  4.         treeSet.add("2");
  5.         treeSet.add("1");
  6.         treeSet.add("3");
  7.         treeSet.add("4");
  8.         System.out.println(treeSet);
  10.         System.out.println("==========================");
  12.         TreeSet<Person> set = new TreeSet<>(new Comparator<Person>() {
  13.             @Override
  14.             public int compare(Person o1, Person o2) {
  15.                 return o1.getAge()-o2.getAge();
  16.             }
  17.         });
  18.         set.add(new Person("柳岩",36));
  19.         set.add(new Person("涛哥",18));
  20.         set.add(new Person("杨幂",32));
  22.         System.out.println(set);
  23.     }
  24. }
  1. public class Person {
  2.     private String name;
  3.     private int age;
  5.     public Person() {
  6.     }
  8.     public Person(String name, int age) {
  9.         this.name = name;
  10.         this.age = age;
  11.     }
  13.     public String getName() {
  14.         return name;
  15.     }
  17.     public void setName(String name) {
  18.         this.name = name;
  19.     }
  21.     public int getAge() {
  22.         return age;
  23.     }
  25.     public void setAge(int age) {
  26.         this.age = age;
  27.     }
  29.     @Override
  30.     public String toString() {
  31.         return "Person{" +
  32.                 "name='" + name + '\'' +
  33.                 ", age=" + age +
  34.                 '}';
  35.     }
  37.     @Override
  38.     public boolean equals(Object o) {
  39.         if (this == o) return true;
  40.         if (o == null || getClass() != o.getClass()) return false;
  41.         Person person = (Person) o;
  42.         return age == person.age &&
  43.                 Objects.equals(name, person.name);
  44.     }
  46.     @Override
  47.     public int hashCode() {
  48.         return Objects.hash(name, age);
  49.     }
  50. }

第三章.TreeMap

  1. 1.概述: TreeMap是Map接口的实现类
  2. 2.特点:
  3.   key唯一
  4.   对key进行排序
  5.   无索引
  6. 3.数据结构:红黑树
  7. 4.构造:
  8.   TreeMap() -> 对key进行自然排序
  9.   TreeMap(Comparator<? super K> comparator) ->对key按照指定规则进行排序
  1.  public class Test01 {
  2.     public static void main(String[] args) {
  3.         TreeMap<String, Integer> treeMap = new TreeMap<>();
  4.         treeMap.put("b",2);
  5.         treeMap.put("a",1);
  6.         treeMap.put("d",4);
  7.         treeMap.put("c",3);
  8.         System.out.println(treeMap);
  10.         System.out.println("=====================");
  12.         TreeMap<Person, String> treeMap1 = new TreeMap<>(new Comparator<Person>() {
  13.             @Override
  14.             public int compare(Person o1, Person o2) {
  15.                 return o1.getAge()-o2.getAge();
  16.             }
  17.         });
  18.         treeMap1.put(new Person("柳岩",36),"湖南");
  19.         treeMap1.put(new Person("涛哥",16),"河北");
  20.         treeMap1.put(new Person("杨幂",32),"北京");
  21.         System.out.println(treeMap1);
  22.     }
  23. }
  1. public class Person {
  2.     private String name;
  3.     private int age;
  5.     public Person() {
  6.     }
  8.     public Person(String name, int age) {
  9.         this.name = name;
  10.         this.age = age;
  11.     }
  13.     public String getName() {
  14.         return name;
  15.     }
  17.     public void setName(String name) {
  18.         this.name = name;
  19.     }
  21.     public int getAge() {
  22.         return age;
  23.     }
  25.     public void setAge(int age) {
  26.         this.age = age;
  27.     }
  29.     @Override
  30.     public String toString() {
  31.         return "Person{" +
  32.                 "name='" + name + '\'' +
  33.                 ", age=" + age +
  34.                 '}';
  35.     }
  37.     @Override
  38.     public boolean equals(Object o) {
  39.         if (this == o) return true;
  40.         if (o == null || getClass() != o.getClass()) return false;
  41.         Person person = (Person) o;
  42.         return age == person.age &&
  43.                 Objects.equals(name, person.name);
  44.     }
  46.     @Override
  47.     public int hashCode() {
  48.         return Objects.hash(name, age);
  49.     }
  50. }

第四章.HashTable和Vector集合(了解)

1.HashTable集合

  1. 1.介绍:
  2.   Map接口的实现类Hashtable, Hashtable类诞生于JDK1.0版本, Map接口诞生于JDK1.2版本.  Hashtable类从JDK1.2开始,改进为实现Map接口
  4. 2.Hashtable类的特点
  5.   a.底层数据结构是哈希表
  6.   b.线程安全的,运行速度慢,被更加先进的HashMap取代
  7.   c.不允许null值,null键, 存储null直接抛出空指针异常
  8.   d.key唯一,无索引,无序
  10. 3.和HashMap的区别
  11.   HashMap:
  12.     线程不安全的,速度快,可以存储null键null值
  13.   HashTable:
  14.     线程安全的,速度慢,不可以存储null键null值,否则会出现空指针异常

2.Vector集合

  1. 1.介绍:
  2.   List接口的实现Vector,命运和Hashtable一样.
  4. 2.Vector类的特点
  5.   a.底层实现结构是数组
  6.   b.数组的默认容量是10,每次扩容是原来的长度*2
  7.   c.线程安全,运行速度慢,被ArrayList取代

第五章.Properties集合(属性集)

  1. 1.Properties 继承  HashTable
  2. 2.特点:
  3.   - 继承Hashtable，底层数据结构是哈希表。
  4.   - 线程安全，运行速度慢。
  5.   - 不允许null值，null键。
  6.   - 此集合存储键值对数据类型固定为String。
  7.   - 可以和IO流结合使用，从流中加载数据。
  8.   - 无序,无索引,key唯一
  9. 3.方法:
  10.    - Object setPropery(String key,String value)，向集合中存储键值对。
  11.    - String getProperty(String key)，获取集合中键对应的值，无此键返回null。
  12.    - Set<String> stringPropertyNames()，集合中的所有键存储到Set集合。
  13.    - void load(输入流对象) ，IO部分讲解。
  1. public class Test01 {
  2.     public static void main(String[] args) {
  3.         Properties properties = new Properties();
  4.         //- Object setPropery(String key,String value)，向集合中存储键值对。
  5.         properties.setProperty("username","root");
  6.         properties.setProperty("password","1234");
  7.         System.out.println(properties);
  8.         //- String getProperty(String key)，获取集合中键对应的值，无此键返回null。
  9.         String username = properties.getProperty("username");
  10.         String password = properties.getProperty("password");
  11.         System.out.println(username+"..."+password);
  12.         //- Set<String> stringPropertyNames()，集合中的所有键存储到Set集合。
  14.         System.out.println("======================");
  16.         Set<String> set = properties.stringPropertyNames();
  17.         for (String key : set) {
  18.             System.out.println(properties.getProperty(key));
  19.         }
  20.     }
  21. }

使用场景:一般都是和properties配置文件结合使用

第六章.集合嵌套

1.List嵌套List

  1. 需求:创建3个List集合，每个集合中分别存储一些字符串，将3个List集合存储到第4个List集合中。
  1. public class Demo01ListInList {
  2.     public static void main(String[] args) {
  3.         ArrayList<String> list1 = new ArrayList<>();
  4.         list1.add("孙悟空");
  5.         list1.add("猪八戒");
  6.         list1.add("沙和尚");
  7.         ArrayList<String> list2 = new ArrayList<>();
  8.         list2.add("宋江");
  9.         list2.add("林冲");
  10.         list2.add("武松");
  11.         ArrayList<String> list3 = new ArrayList<>();
  12.         list3.add("刘备");
  13.         list3.add("关羽");
  14.         list3.add("张飞");
  16.         //创建一个专门存储集合的List
  17.         ArrayList<ArrayList<String>> list = new ArrayList<>();
  18.         list.add(list1);
  19.         list.add(list2);
  20.         list.add(list3);
  22.         //遍历
  23.         //先遍历大集合,将每一个小集合遍历出来
  24.         for (ArrayList<String> arrayList : list) {
  25.             //在遍历每一个小集合,将元素从小集合中获取出来
  26.             for (String s : arrayList) {
  27.                 System.out.println(s);
  28.             }
  29.         }
  30.     }
  31. }

2.List嵌套Map

  1. 1班级有第三名同学，学号和姓名分别为：1=张三，2=李四，3=王五，2班有三名同学，学号和姓名分别为：1=黄晓明，2=杨颖，3=刘德华，4=朱丽倩，请将同学的信息以键值对的形式存储到2个Map集合中，在将2个Map集合存储到List集合中。
  1. public class Demo02ListInMap {
  2.     public static void main(String[] args) {
  3.         HashMap<Integer, String> map1 = new HashMap<>();
  4.         map1.put(1,"张三");
  5.         map1.put(2,"李四");
  6.         HashMap<Integer, String> map2 = new HashMap<>();
  7.         map2.put(1,"黄晓明");
  8.         map2.put(2,"杨颖");
  10.         ArrayList<HashMap<Integer, String>> list = new ArrayList<>();
  11.         list.add(map1);
  12.         list.add(map2);
  14.         //遍历
  15.         //先遍历List将每个小Map遍历出来
  16.         for (HashMap<Integer, String> map : list) {
  17.             //再遍历每一个map,将map中的键值对获取出来
  18.             Set<Map.Entry<Integer, String>> entries = map.entrySet();
  19.             for (Map.Entry<Integer, String> entry : entries) {
  20.                 System.out.println(entry.getKey()+"..."+entry.getValue());
  21.             }
  22.         }
  23.     }
  24. }

3.Map嵌套Map

  1. - JavaSE  集合 存储的是 学号 键，值学生姓名
  2.   - 1  张三
  3.   - 2  李四
  4. - JavaEE
  5.   - 1  王五
  6.   - 2  赵柳
  1. public class Demo03MapInMap {
  2.     public static void main(String[] args) {
  3.         HashMap<Integer, String> map1 = new HashMap<>();
  4.         map1.put(1,"张三");
  5.         map1.put(2,"李四");
  6.         HashMap<Integer, String> map2 = new HashMap<>();
  7.         map2.put(1,"王五");
  8.         map2.put(2,"赵六");
  10.         HashMap<String, HashMap<Integer, String>> hashMap = new HashMap<>();
  11.         hashMap.put("JavaSE",map1);
  12.         hashMap.put("JavaEE",map2);
  14.         //遍历
  15.         //先遍历大Map,将每一个小Map遍历出来
  16.         Set<String> set = hashMap.keySet();
  17.         for (String key : set) {
  18.             HashMap<Integer, String> map = hashMap.get(key);
  19.             //遍历小map,将小map中的key和value遍历出来
  20.             Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
  21.             for (Map.Entry<Integer, String> entry : entrySet) {
  22.                 Integer key1 = entry.getKey();
  23.                 String value1 = entry.getValue();
  24.                 System.out.println(key1+"..."+value1);
  25.             }
  26.         }
  27.     }
  28. }

第七章.哈希表结构存储过程

day16[Map集合] - 图4

  1. 1.HashMap底层数据数据结构:哈希表
  2. 2.jdk7:哈希表 = 数组+链表
  3.   jdk8:哈希表 = 数组+链表+红黑树
  4. 3.
  5.   先算哈希值,此哈希值在HashMap底层经过了特殊的计算得出
  6.   如果哈希值不一样,直接存
  7.   如果哈希值一样,再去比较内容,如果内容不一样,也存
  8.   如果哈希值一样,内容也一样,直接去重复(后面的value将前面的value覆盖)
  10.   哈希值一样->哈希冲突(哈希碰撞)
  11. 4.要知道的点:
  12.   a.在不指定长度时,哈希表中的数组默认长度为16,HashMap创建出来,一开始没有创建长度为16的数组
  13.   b.什么时候创建的长度为16的数组呢?在第一次put的时候,底层会创建长度为16的数组
  14.   c.哈希表中有一个数据加[加载因子]->默认为0.75->代表党元素存储到百分之75的时候要扩容了->2倍
  15.   d.如果对个元素出现了哈希值一样,内容不一样时,就会在同一个索引上以链表的形式存储,当链表长度>8并且当前数据长度>64时,链表就会改成使用红黑树存储
  16.   e.加入红黑树目的:查询快
  1. 外面笔试时可能会问到的变量
  2. default_initial_capacity:HashMap默认容量  16
  3. default_load_factor:HashMap默认加载因子   0.75
  4. threshold:扩容的临界值   等于   容量*0.75 = 12
  5. treeify_threshold:链表长度默认值,转为红黑树:8
  6. min_treeify_capacity:链表被树化时最小的数组容量:64

第八章.哈希表源码分析

1.HashMap无参数构造方法的分析

  1. //HashMap中的静态成员变量
  2. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  3. public HashMap() {
  4.     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  5. }

解析：使用无参数构造方法创建HashMap对象，将加载因子设置为默认的加载因子，loadFactor=0.75F。

2.HashMap有参数构造方法分析

  1. HashMap(int initialCapacity, float loadFactor) ->创建Map集合的时候指定底层数组长度以及加载因子
  3. public HashMap(int initialCapacity, float loadFactor) {
  4.     if (initialCapacity < 0)
  5.         throw new IllegalArgumentException("Illegal initial capacity: " +
  6.     initialCapacity);
  7.     if (initialCapacity > MAXIMUM_CAPACITY)
  8.         initialCapacity = MAXIMUM_CAPACITY;
  9.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  10.         throw new IllegalArgumentException("Illegal load factor: " +
  11.     loadFactor);
  12.     this.loadFactor = loadFactor;
  13.     this.threshold = tableSizeFor(initialCapacity);//10
  14. }

解析：带有参数构造方法，传递哈希表的初始化容量和加载因子

  • 如果initialCapacity（初始化容量）小于0，直接抛出异常。
  • 如果initialCapacity大于最大容器，initialCapacity直接等于最大容器
    • MAXIMUM_CAPACITY = 1 << 30 是最大容量 (1073741824)
  • 如果loadFactor（加载因子）小于等于0，直接抛出异常
  • tableSizeFor（initialCapacity）方法计算哈希表的初始化容量。
    • 注意：哈希表是进行计算得出的容量，而初始化容量不直接等于我们传递的参数。

3.tableSizeFor方法分析

  1. static final int tableSizeFor(int cap) {
  2.     int n = cap - 1;
  3.     n |= n >>> 1;
  4.     n |= n >>> 2;
  5.     n |= n >>> 4;
  6.     n |= n >>> 8;
  7.     n |= n >>> 16;
  8.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  9. }
  11. 8  4  2  1规则->无论指定了多少容量,最终经过tableSizeFor这个方法计算之后,都会遵循8421规则去初始化列表容量

解析：该方法对我们传递的初始化容量进行位移运算，位移的结果是 8 4 2 1 码

  • 例如传递2，结果还是2，传递的是4，结果还是4。
  • 例如传递3，结果是4，传递5，结果是8，传递20，结果是32。

4.Node 内部类分析

哈希表是采用数组+链表的实现方法，HashMap中的内部类Node非常重要，证明HashSet是一个单向链表

  1.  static class Node<K,V> implements Map.Entry<K,V> {
  2.      final int hash;
  3.      final K key;
  4.      V value;
  5.      Node<K,V> next;
  6.  Node(int hash, K key, V value, Node<K,V> next) {
  7.      this.hash = hash;
  8.      this.key = key;
  9.      this.value = value;
  10.      this.next = next;
  11. }

解析：内部类Node中具有4个成员变量

  • hash，对象的哈希值
  • key，作为键的对象
  • value，作为值得对象（讲解Set集合，不牵扯值得问题）
  • next，下一个节点对象

5.存储元素的put方法源码

  1. public V put(K key, V value) {
  2.     return putVal(hash(key), key, value, false, true);
  3. }

解析：put方法中调研putVal方法，putVal方法中调用hash方法。

  • hash(key)方法：传递要存储的元素，获取对象的哈希值
  • putVal方法，传递对象哈希值和要存储的对象key

6.putVal方法源码

  1. Node<K,V>[] tab; Node<K,V> p; int n, i;
  2.     if ((tab = table) == null || (n = tab.length) == 0)
  3.         n = (tab = resize()).length;

解析：方法中进行Node对象数组的判断，如果数组是null或者长度等于0，那么就会调研resize()方法进行数组的扩容。

7.resize方法的扩容计算

  1.  if (oldCap > 0) {
  2.      if (oldCap >= MAXIMUM_CAPACITY) {
  3.          threshold = Integer.MAX_VALUE;
  4.          return oldTab;
  5.      }
  6.      else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  7.               oldCap >= DEFAULT_INITIAL_CAPACITY)
  8.          newThr = oldThr << 1; // double threshold
  9. }

解析：计算结果，新的数组容量=原始数组容量<<1，也就是乘以2。

8.确定元素存储的索引

  1. if ((p = tab[i = (n - 1) & hash]) == null)
  2.      tab[i] = newNode(hash, key, value, null);

解析：i = (数组长度 - 1) & 对象的哈希值，会得到一个索引，然后在此索引下tab[i]，创建链表对象。

不同哈希值的对象，也是有可能存储在同一个数组索引下。

  1. 其中resize()扩容的方法,默认是16
  2.  tab[i] = newNode(hash, key, value, null);->将元素放在数组中  i就是索引
  4.  i = (n - 1) & hash
  5.      0000 0000 0000 0000 0000 0000 0000 1111->15
  6.                                                     &   0&0=0 0&1=0 1&1=1
  7.      0000 0000 0000 0001 0111 1000 0110 0011->96355
  8. --------------------------------------------------------
  9.      0000 0000 0000 0000 0000 0000 0000 0011->3
  1.      0000 0000 0000 0000 0000 0000 0000 1111->15
  2.                                                     &   0&0=0 0&1=0 1&1=1
  3.      0000 0000 0001 0001 1111 1111 0001 0010->1179410
  4. --------------------------------------------------------
  5.      0000 0000 0000 0000 0000 0000 0000 0010->2

9.遇到重复哈希值的对象

  1.  Node<K,V> e; K k;
  2.  if (p.hash == hash &&
  3.      ((k = p.key) == key || (key != null && key.equals(k))))
  4.          e = p;

解析：如果对象的哈希值相同，对象的equals方法返回true，判断为一个对象，进行覆盖操作。

  1.  else {
  2.      for (int binCount = 0; ; ++binCount) {
  3.          if ((e = p.next) == null) {
  4.              p.next = newNode(hash, key, value, null);
  5.          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  6.              treeifyBin(tab, hash);
  7.          break;
  8.  }

解析：如果对象哈希值相同，但是对象的equals方法返回false，将对此链表进行遍历，当链表没有下一个节点的时候，创建下一个节点存储对象。