• java中常用的集合

    目录

     几种常用的集合为什么要用集合

    List集合

    Set集合

    Map集合

    常见实现类

    一、HashMap底层实现原理解析

    Junit架包下载

     几种常用的集合
    为什么要用集合

    当我们需要操作一些类型相同的数据时，就会想到运用集合了，那为什么不用数组呢？因为Java是面向对象语言，为了操作一些对象，就得把这些对象存储起来，而集合提供的的一些API很方便我们去操作存储的Java对象。
    集合的分类
    1、Collection:Collection是List、Set、Queue的接口。
    2、Iterator:迭代器，主要用来遍历集合。
    3、Map:是映射表(键值对)的接口。

    List集合


    List是有序集合有三个实现类，分别是ArrayList、Vector、LinkedList。
    集合的常用操作
    add(数据):添加数据
    remove(数据):删除数据
    indexOf(数据):返回数据在集合中第一次出现式的索引位置的值
    contains():该方法是判断字符串中是否有子字符串，有返回true。没有返回false。
    clear():将list中的对象变成垃圾清空。
    remove，contains，indexOf三个方法会默认去调用equals方法。
     

    ArrayList
    ArrayList最常用的集合，它的底层是一个数组，每个元素之间不能有间隔。它适合查找，不适合增删，从中间位置增删时，要对数组进行移动、复制、所费的代价比较高。当它的大小不满足时时会创建一个新数组，然后将旧数组的数据复制到新数组。


    Vector 线程安全的
    Vector内部实现类似于ArrayList。它支持线程同步，某时刻只能有一个线程能够写Vector。但花费很高，所以访问Vector比访问ArrayList慢。

    比vector快并且又线程安全的

    CopyOnWriteArrayList它是ArrayList的线程安全的变体，大概原理就是：初始化的时候只有一个容器，很长一段时间，这个容器数据，数量等没有发生变化的时候，大家（大多数线程）都是读取（假设这段时间里只发生读取操作）同一个容器中的数据，这样大家读取到数据都是唯一，一致，安全的，但是后来有人往里面增加了一个数据，这个时候CopyOnWriteArrayList底层实现添加的原理是先copy出一个容器（简称副本），再往新的容器里添加这个新的数据，最后把新的容器的引用地址赋值给之前旧的容器地址，但是在添加这个数据期间，其他线程如果要读取数据，仍然是读取旧的容器里的数据 保证最终一致性。

    LinkindeList
    LinkedList底层是一个双向链表，所以很适合做插入、删除的操作。LinkedList继承于AbstractSequentialList，它同时也实现了Deque，Queue接口。它还提供了List接口中没有的方法，专门用于操作表头和表尾的元素，可以当堆栈、队列、双向链表使用 但不适合读 。

    LinkindeList特有的方法

    1.     1. public void addFirst(E e) 将指定元素插入到次列表的开头
    2.     2. public void addLast(E e) 将指定元素添加到此列表的结尾
    3.     3. public E getFirst() 返回此列表的第一个元素
    4.     4. public E getLast() 返回此列表的最后一个元素
    5.     5. public E removeFirst() 移除并返回此列表的第一个元素
    6.     6. public E removeLast() 移除并返回此列表的最后一个元素
    7.     7. public E pop() 从此列表所表示的堆栈处弹出一个元素
    8.     8. public void push(E e) 将元素推入此列表所表示的堆栈

    List集合的遍历方式
    普通for循环

    1.  ArrayList<String> a = new ArrayList<>();
    2.         a.add("sdf");
    3.         for (int i = 0 ; i<a.size(); i++){
    4.             String s = (String) a.get(i);
    5.             System.out.println(s);
    6.         }

    foreach循环

    1. ArrayList<String> a = new ArrayList<>();
    2.         a.add("sdf");
    3.         a.add("2222");
    4.         for (String value:a) {
    5.             System.out.println(value);
    6.         }

    迭代器

    1. ArrayList<String> a = new ArrayList<>();
    2.         a.add("sdf");
    3.         a.add("2222");
    4.         Iterator iterator = a.iterator();
    5.         while (iterator.hasNext()){
    6.             String s = (String) iterator.next();
    7.             System.out.println(s);
    8.         }

    List去重复数据方法很简单 使用set集合特性去除重复数据

    1. List<Student> list=new ArrayList<>(new HashSet<>(this.list));
    2. System.out.println(list);
    关于java中的传递 
    1. //讲述关于java的引用传递
    2. 	@Test
    3. 	public void testUpdate() {
    4. 		List<Student> lst = updateList02(list);
    5. 		lst.forEach(t->System.out.println(t));
    6. 		System.out.println("=========================");
    7. 		list.forEach(t->System.out.println(t));
    8. 	}
    9. 	
    10. 	
    11. 	private List<Student> updateList01(List<Student> temp) {
    12. 		List<Student> tt = temp;
    13. 		for(Student stu: tt) {
    14. 			stu.setName("EEEEEEEE");
    15. 		}
    16. 		return tt;
    17. 	}

     

    List删除需要注意的点

    在实际开发中有时候会碰到这样的场景，需要将一个list集合中的某些特定的元素给删除掉，这个时候用可以用List提供的remove方法来实现需求。

    List中的remove方法传入的参数可以是集合的下标，也可以是集合中一个元素，也可以是一个集合。
    错误使用示例一：

    这里我使用的是增强for循环，会发现直接报错。

    List集合的一个特点是它其中的元素时有序的，也就是说元素的下标是根据插入的顺序来的，在删除头部或者中间的一个元素后，后面的元素下标会往前移动。循环的时候就会出现问题。

    1. @Data
    2. @AllArgsConstructor
    3. public class Person {
    4.     private String id;
    5.     private String name;
    6.  
    7.     public static void main(String[] args) {
    8.         List<Person> lists = new ArrayList<>();
    9.         lists.add(new Person("1", "张三"));
    10.         lists.add(new Person("2", "王五"));
    11.         lists.add(new Person("3", "李六"));
    12.         lists.add(new Person("4", "哈哈"));
    13.  
    14.         for (Person person4 : lists) {
    15.             if (person4.getId().equals("2")) {
    16.                 lists.remove(person4);
    17.             }
    18.         }
    19.     }
    20. }

    解决方案一：不要用for-each遍历，换成迭代器遍历，并且不要用list.remove()方法移除对象，用迭代器的方法iterator.remove()移除对象。 

    （1）迭代器遍历方式， 适用于连续内存存储方式，比如数组、 ArrayList（其实 ArrayList底层实现也是数组形式）。 缺点是只能从头开始遍历， 优点是可以边遍历边删除

    （2）arraylist每次遍历的时候会去判断该集合是否被修改过，调用的方法是checkForComodification()。 如果被修改过ConcurrentModificationException异常。

    （3）如何判断是否修改呢，主要是通过维护2个变量来实现，modCount记录了修改次数，expectedModCount记录期望修改次数。 通过iterator.remove()进行的删除操作，会同时修改modCount、ConcurrentModificationException; 而通过list.remove(object/index)，则只会修改modCount。 这也是fast-fail机制

    注意迭代器的删除不适用CopyOnWriteArrayList因为CopyOnWriteArrayList是用的写时复制 所有我们去用迭代器的删除会报异常 不支持的操作Excep 所以我们只能用CopyOnWriteArrayList自带的remove

    1. @Data
    2. @AllArgsConstructor
    3. public class Person {
    4.     private String id;
    5.     private String name;
    6.  
    7.     public static void main(String[] args) {
    8.         List<Person> lists = new ArrayList<>();
    9.         lists.add(new Person("1", "张三"));
    10.         lists.add(new Person("2", "王五"));
    11.         lists.add(new Person("3", "李六"));
    12.         lists.add(new Person("4", "哈哈"));
    13.  
    14.         Iterator<Person> iterator = lists.iterator();
    15.         while (iterator.hasNext()){
    16.             Person next = iterator.next();
    17.             if(next.getId().equals("2")){
    18.                 iterator.remove();
    19.             }
    20.         }
    21.  
    22.         lists.forEach(item-> System.out.println(item));
    23.     }
    24. }

    解决方案二：在循环中（比如for循环）使用remove方法时，注意要从List集合的最后一个元素开始遍历。

    1. @Data
    2. @AllArgsConstructor
    3. public class Person {
    4.     private String id;
    5.     private String name;
    6.  
    7.     public static void main(String[] args) {
    8.         List<Person> lists = new ArrayList<>();
    9.         lists.add(new Person("1", "张三"));
    10.         lists.add(new Person("2", "王五"));
    11.         lists.add(new Person("3", "李六"));
    12.         lists.add(new Person("4", "哈哈"));
    13.  
    14.         for (int i = lists.size() - 1; i >= 0; i--) {
    15.             if (lists.get(i).getId().equals("2")) {
    16.                 lists.remove(i);
    17.             }
    18.         }
    19.  
    20.         lists.forEach(item-> System.out.println(item));
    21.     }
    22. }

    错误使用示例二：

    这个示例当中没有使用增强for，而是普通的循环，没有报错，但是结果不是我们想要的结果。

    1. @Test
    2. public void myList(){
    3.         
    4.             List<Integer> list = new ArrayList<>();
    5.             list.add(1);
    6.             list.add(2);
    7.             list.add(3);
    8.             list.add(3);
    9.             list.add(4);
    10.             for(int i = 0; i<list.size(); i++) {
    11.                 if(list.get(i) == 3) //第一次进来
    12.                     list.remove(i);
    13.             }
    14.  
    15.             list.forEach(item-> System.out.println(item));
    16.             
    17. }

    解决方法 原因：假如我们删除的是3 看上面可知3的下标是2那我们吧下标为2的删除后数组特性后面一位会往上面移那么本来下标为3的数据下标就会变为2 循环已经循环过2了那么他就会跳过他后面数据的检查 哪我们可以

    在删除的时候改成i-- 减减在后面那么第一次进来的时候是对i没有影响的因为要运行后再回减

    Debug演示 

    1. @Test
    2. public void myList(){
    3.         
    4.             List<Integer> list = new ArrayList<>();
    5.             list.add(1);
    6.             list.add(2);
    7.             list.add(3);
    8.             list.add(3);
    9.             list.add(4);
    10.             for(int i = 0; i<list.size(); i++) {
    11.                 if(list.get(i) == 3) //第一次进来
    12.                     list.remove(i--);
    13.             }
    14.  
    15.             list.forEach(item-> System.out.println(item));
    16.             
    17. }

    Set集合


    Set集合是一个无序集合，Set中重复的数据只能添加一遍，JVM用hashcode和equals方法来判断是否重复，只有两个方法返回一致则认为是重复，先调用hashcode方法如果返回不一致则不调用equals方法，如果返回一致则调用equals方法再来判断是否一致。 

    所以使用时如果加的是实体对象那么实体对象要实现无重复数据要把equals和hashcode重写

    Set 集合的遍历与List集合的遍历类似，只是它是无序的不能用普通for循环遍历
    Iterator迭代器
    Iterator不是一个集合，它是一个访问List 和Set集合的方法
    它的基本操作有
    hasNext():如果有还元素可以迭代则返回true
    next():返回迭代的下一个元素。
    remove():将迭代器返回的元素删除。
    常见实现类
    HashSet:HashSet存储元素的顺序并不是按照存入时的顺序而是按照哈希值来存取的。

    HashSet是Set接口的典型实现，大多数时候使用Set集合时就是使用这个实现类。HashSet按Hash算法来存储集合中的元素，因此具有很好的存取和查找性能。底层数据结构是哈希表。
    哈希表
    一个元素为链表的数组，综合了数组与链表的优点。

    HashSet具有以下特点：

    不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也可能发生变化；
    HashSet不是同步的；
    集合元素值可以是null；
    内部存储机制

    当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode方法来得到该对象的hashCode值，然后根据该hashCode值决定该对象在HashSet中的存储位置。如果有两个元素通过equals方法比较true，但它们的hashCode方法返回的值不相等，HashSet将会把它们存储在不同位置，依然可以添加成功。
    也就是说。HashSet集合判断两个元素的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode方法返回值也相等。

    靠元素重写hashCode方法和equals方法来判断两个元素是否相等，如果相等则覆盖原来的元素，依此来确保元素的唯一性

    实例：
    没有重写hashCode和equals方法

    1.         Student s1 = new Student("小龙女", 23);
    2.         Student s2 = new Student("任盈盈", 24);
    3.         Student s3 = new Student("小龙女", 23);
    4.         Student s4 = new Student("东方不败", 25);
    5.         Student s5 = new Student("伊琳", 29);
    6.         Student s6 = new Student("周芷若", 30);
    7.         HashSet<Student> hashSet = new HashSet<>();
    8.         hashSet.add(s1);
    9.         hashSet.add(s2);
    10.         hashSet.add(s3);
    11.         hashSet.add(s4);
    12.         hashSet.add(s5);
    13.         hashSet.add(s6);
    14.         for (Student student : hashSet) {
    15.             System.out.println(student.getName()+"=="+student.getAge());
    16.         }
    17.     
    18.

    那么就会输出 重复数据不会被刷掉

     

    重写了hashCode和equals方法

    1. package com.zking.map;
    2.  
    3. import java.util.Objects;
    4.  
    5. public class Student {
    6.     private  String name;
    7.     private Integer age;
    8.  
    9.     public Student(String name, Integer age) {
    10.         this.name = name;
    11.         this.age = age;
    12.     }
    13.  
    14.     public String getName() {
    15.         return name;
    16.     }
    17.  
    18.     public void setName(String name) {
    19.         this.name = name;
    20.     }
    21.  
    22.     public Integer getAge() {
    23.         return age;
    24.     }
    25.  
    26.     public void setAge(Integer age) {
    27.         this.age = age;
    28.     }
    29.  
    30.     @Override
    31.     public String toString() {
    32.         return "Student{" +
    33.                 "name='" + name + '\'' +
    34.                 ", age=" + age +
    35.                 '}';
    36.     }
    37.  
    38.     @Override
    39.     public boolean equals(Object o) {
    40.         if (this == o) return true;
    41.         if (o == null || getClass() != o.getClass()) return false;
    42.         Student student = (Student) o;
    43.         return Objects.equals(name, student.name) && Objects.equals(age, student.age);
    44.     }
    45.  
    46.     @Override
    47.     public int hashCode() {
    48.         return Objects.hash(name, age);
    49.     }
    50. }

    那么结果就是


    TreeSet的作用是提供一个有序的Set集合，对新添加的元素按照指定的顺序排序。Integer和String对象都可以进行默认的排序，而自定义对象必须实现Comparable并重写相应的ComapreTo方法。

    直接输出对象的结果

    1. public class TreeSetDemo02 {
    2. 	public static void main(String[] args) {
    3. 		TreeSet<Student> ts=new TreeSet<Student>();		
    4. 		//创建元素对象
    5. 		Student s1=new Student("zhangsan",20);
    6. 		Student s2=new Student("lis",22);
    7. 		Student s3=new Student("wangwu",24);
    8. 		Student s4=new Student("chenliu",26);
    9. 		Student s5=new Student("zhangsan",22);
    10. 		Student s6=new Student("qianqi",24);
    11. 		
    12. 		//将元素对象添加到集合对象中
    13. 		ts.add(s1);
    14. 		ts.add(s2);
    15. 		ts.add(s3);
    16. 		ts.add(s4);
    17. 		ts.add(s5);
    18. 		ts.add(s6);
    19. 		
    20. 		//遍历
    21. 		for(Student s:ts){
    22. 			System.out.println(s.getName()+"-----------"+s.getAge());
    23. 		}
    24. 	}
    25. }

    Student类：

    1. package com.zking.map;
    2.  
    3. import java.util.Objects;
    4.  
    5. public class Student {
    6.     private  String name;
    7.     private Integer age;
    8.  
    9.     public Student(String name, Integer age) {
    10.         this.name = name;
    11.         this.age = age;
    12.     }
    13.  
    14.     public String getName() {
    15.         return name;
    16.     }
    17.  
    18.     public void setName(String name) {
    19.         this.name = name;
    20.     }
    21.  
    22.     public Integer getAge() {
    23.         return age;
    24.     }
    25.  
    26.     public void setAge(Integer age) {
    27.         this.age = age;
    28.     }
    29.  
    30.     @Override
    31.     public String toString() {
    32.         return "Student{" +
    33.                 "name='" + name + '\'' +
    34.                 ", age=" + age +
    35.                 '}';
    36.     }
    37.  
    38.     @Override
    39.     public boolean equals(Object o) {
    40.         if (this == o) return true;
    41.         if (o == null || getClass() != o.getClass()) return false;
    42.         Student student = (Student) o;
    43.         return Objects.equals(name, student.name) && Objects.equals(age, student.age);
    44.     }
    45.  
    46.     @Override
    47.     public int hashCode() {
    48.         return Objects.hash(name, age);
    49.     }
    50. }

    运行结果

    原因分析：

    由于不知道该安照那一中排序方式排序，所以会报错。

    解决方法：

        1.自然排序

    2.比较器排序

    实现排序的两种方式

    1.Student类中实现  Comparable<T>接口

    1. package com.zking.map;
    2.  
    3. import java.util.Objects;
    4.  
    5. public class Student implements Comparable<Student>{
    6.     private  String name;
    7.     private Integer age;
    8.  
    9.     public Student(String name, Integer age) {
    10.         this.name = name;
    11.         this.age = age;
    12.     }
    13.  
    14.     public String getName() {
    15.         return name;
    16.     }
    17.  
    18.     public void setName(String name) {
    19.         this.name = name;
    20.     }
    21.  
    22.     public Integer getAge() {
    23.         return age;
    24.     }
    25.  
    26.     public void setAge(Integer age) {
    27.         this.age = age;
    28.     }
    29.  
    30.     @Override
    31.     public String toString() {
    32.         return "Student{" +
    33.                 "name='" + name + '\'' +
    34.                 ", age=" + age +
    35.                 '}';
    36.     }
    37.  
    38.     @Override
    39.     public boolean equals(Object o) {
    40.         if (this == o) return true;
    41.         if (o == null || getClass() != o.getClass()) return false;
    42.         Student student = (Student) o;
    43.         return Objects.equals(name, student.name) && Objects.equals(age, student.age);
    44.     }
    45.  
    46.     @Override
    47.     public int hashCode() {
    48.         return Objects.hash(name, age);
    49.     }
    50.  
    51.  
    52.     @Override
    53.     public int compareTo(Student o) {
    54.         //判断如果两个年龄都一样排序 如果不判断会缺失数据 如果年龄相同数据会直接丢失 感兴趣可以注释下面代码测试
    55.         if(this.age -o.age==0){
    56.             //要么返回正数要么返回负数 如果有id也可以根据id排序
    57.             return  -1;
    58.         }
    59.         //按照年龄进行排序
    60.         return this.age -o.age;
    61.     }
    62. }

    运行结果 改方法返回正数为正序 烦则倒序 返回0不处理会覆盖

    如果想倒序那么把compareTo方法改为

    1.  @Override
    2.     public int compareTo(Student o) {
    3.         //判断如果两个年龄都一样排序 如果不判断会缺失数据 如果年龄相同数据会直接丢失 感兴趣可以注释下面代码测试
    4.         if(this.age -o.age==0){
    5.             //要么返回正数要么返回负数 如果有id也可以根据id排序
    6.             return  -1;
    7.         }
    8.         
    9.         //按照年龄进行排序
    10.         return o.age -this.age;
    11.     }

    2.重写Comparable接口中的Compareto方法  此方法会覆盖覆盖（重写）实体中实现的排序对象Comparator的compareTo方法

    1. package com.zking.map;
    2.  
    3. import java.util.Comparator;
    4. import java.util.TreeSet;
    5.  
    6. public class TreeSetDemo02 {
    7. 	public static void main(String[] args) {
    8. 		TreeSet<Student> ts=new TreeSet<Student>(new Comparator<Student>() {
    9. 			@Override
    10. 			public int compare(Student o1, Student o2) {
    11. 				//判断如果两个年龄都一样排序 如果不判断会缺失数据 如果年龄相同数据会直接丢失 感兴趣可以注释下面代码测试
    12. 				if(o2.getAge() -o1.getAge()==0){
    13. 					//要么返回正数要么返回负数 如果有id也可以根据id排序
    14. 					return  -1;
    15. 				}
    16.  
    17. 				//按照年龄进行排序
    18. 				return o2.getAge() -o1.getAge();
    19. 			}
    20. 		});
    21. 		//创建元素对象
    22. 		Student s1=new Student("zhangsan",20);
    23. 		Student s2=new Student("lis",22);
    24. 		Student s3=new Student("wangwu",24);
    25. 		Student s4=new Student("chenliu",26);
    26. 		Student s5=new Student("zhangsan",22);
    27. 		Student s6=new Student("qianqi",24);
    28. 		
    29. 		//将元素对象添加到集合对象中
    30. 		ts.add(s1);
    31. 		ts.add(s2);
    32. 		ts.add(s3);
    33. 		ts.add(s4);
    34. 		ts.add(s5);
    35. 		ts.add(s6);
    36. 		
    37. 		//遍历
    38. 		for(Student s:ts){
    39. 			System.out.println(s.getName()+"-----------"+s.getAge());
    40. 		}
    41. 	}
    42. }

     运行效果是一样的 

    Map集合


    Map是一个接口，存储的是键值对。Map存储的键如果重复则会覆盖值。重复的意思是hashcode和equals方法做比较，只有两个都一致则会认为是重复。
    常用操作
    put():添加数据。
    get(key):获取单个数据。
    keySet():获得键的集合。
    values():获得所有值的集合。
    entrySet():获得所有的entry对象(键值的集合)。
    isEmpty():判断集合是否为空
    size():获得数据的个数。
    remove(key):删除某个值。


    常见实现类


    HashMap在JDK1.8的底层是(数组+链表+红黑树)根据键的hashcode存储数据，大多是情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历的顺序不确实的。HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。

    一、HashMap底层实现原理解析

    我们常见的有数据结构有三种结构：

    数组结构
    链表结构
    哈希表结构
    下面我们来看看各自的数据结构的特点：
    1）数组结构： 存储区间连续、内存占用严重、空间复杂度大

    优点：随机读取和修改效率高，原因是数组是连续的（随机访问性强，查找速度快）
    缺点：插入和删除数据效率低，因插入数据，这个位置后面的数据在内存中都要往后移动，且大小固定不易动态扩展。
    2）链表结构：存储区间离散、占用内存宽松、空间复杂度小

    优点：插入删除速度快，内存利用率高，没有固定大小，扩展灵活
    缺点：不能随机查找，每次都是从第一个开始遍历（查询效率低）
    3）哈希表结构：结合数组结构和链表结构的优点，从而实现了查询和修改效率高，插入和删除效率也高的一种数据结构

    HashMap底层是哈希表结构

    HashMap中的put()和get()的实现原理：
    1）map.put(k,v)实现原理
    （1）首先将k,v封装到Node对象当中（节点）。
    （2）然后它的底层会调用K的hashCode()方法得出hash值。
    （3）通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。
    2、map.get(k)实现原理
    (1)先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
    (2)通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。

    为何随机增删、查询效率都很高的原因是？
    增删是在链表上完成的，而查询只需扫描部分，则效率高。
    HashMap集合的key，会先后调用两个方法，hashCode and equals方法，这这两个方法都需要重写。

    为什么放在hashMap集合key部分的元素需要重写equals方法？
    因为equals方法默认比较的是两个对象的内存地址

    二、HashMap红黑树原理分析
    相比 jdk1.7 的 HashMap 而言，jdk1.8最重要的就是引入了红黑树的设计，红黑树除了插入操作慢其他操作都比链表快，当hash表的单一链表长度超过 8 个的时候，数组长度大于64，链表结构就会转为红黑树结构。当红黑树上的节点数量小于6个，会重新把红黑树变成单向链表数据结构。
    为什么要这样设计呢？好处就是避免在最极端的情况下链表变得很长很长，在查询的时候，效率会非常慢。


    红黑树查询：其访问性能近似于折半查找，时间复杂度 O(logn)；
    链表查询：这种情况下，需要遍历全部元素才行，时间复杂度 O(n)；
    简单的说，红黑树是一种近似平衡的二叉查找树，其主要的优点就是“平衡“，即左右子树高度几乎一致，以此来防止树退化为链表，通过这种方式来保障查找的时间复杂度为 log(n)。


    关于红黑树的内容，网上给出的内容非常多，主要有以下几个特性：
    1、每个节点要么是红色，要么是黑色，但根节点永远是黑色的；

    2、每个红色节点的两个子节点一定都是黑色；

    3、红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）；

    4、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

    5、所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
    在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件 3 或条件 4，需要通过调整使得查找树重新满足红黑树的条件。

    三、HashMap的原理1.7 和1.8 的区别
    jdk1.7中底层是由数组+链表实现；jdk1.8中底层是由数组+链表/红黑树实现
    可以存储null键和null值，线程不安全
    初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂
    扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
    当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀
    hash冲突
    当两个key通过hashCod计算相同时（其实hashCode是随机产生的，是有可能hashCode相同）,则发生了hash冲突，开放定址法、再哈希法、链地址法、建立公共溢出区
    HashMap解决hash冲突的方式是用链表。当发生hash冲突时，则将存放在数组中的Entry设置为新值的next，说白就是比如A和B都hash后都映射到下标i中，之前已经有A了，当map.put(B)时，将B放到下标i中，A则为B的next，所以新值存放在数组中，旧值在新值的链表上

    开放定址法：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中
    再哈希法：同时构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。
    链地址法：这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
    建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
     

    ConcurrentHashMap 线程安全，比HashTable性能高
    HashTable  线程安全，不太常用

    用法和HashMap差不多

    1. @Test
    2. 	public void demo12() {
    3. 		Hashtable<String,String> table = new Hashtable();
    4. 		table.put("1", "xx");
    5. 		table.forEach((key,val) -> System.out.println(key + ": " + val));
    6. 	}
    7. 	
    8. 	
    9. 	@Test
    10. 	public void demo13() {
    11. //		线程安全并且速度比Hashtable快
    12. 		ConcurrentHashMap<String,String> table = new ConcurrentHashMap<>();
    13. 		table.put("1", "xx");
    14. 		table.forEach((key,val) -> System.out.println(key + ": " + val));
    15. 	}

    TreeMap key值按一定的顺序排序    添加或获取元素时性能较HashMap慢 因为需求维护内部的红黑树
    LinkHashMap LinkedHashMap是有序的，且默认为插入顺序  当我们希望有顺序地去存储key-value时，就需要使用LinkedHashMap了

    Junit架包下载

    注意下列代码运行需要配置junit eclipse 中自带配置一下就好了 一定要选junit 4或者以上的  或者下架包也行  架包下载  Junit中JAR包.rar - 蓝奏云

    1. package com.zking.jee02;
    2.  
    3. import java.util.Comparator;
    4. import java.util.Iterator;
    5. import java.util.LinkedHashMap;
    6. import java.util.Map;
    7. import java.util.Map.Entry;
    8. import java.util.Set;
    9. import java.util.TreeMap;
    10.  
    11. import org.junit.Before;
    12. import org.junit.Test;
    13.  
    14. import com.zking.jee02.model.Student;
    15.  
    16. public class TreeMapTest {
    17. 	
    18. 	private TreeMap<String,Student> treeMap;
    19. 	
    20. 	@Before
    21. 	public void setup() {
    22. 		treeMap = new TreeMap<String,Student>(new Comparator<String>() {
    23.  
    24. 			@Override
    25. 			public int compare(String o1, String o2) {
    26. 				// TODO Auto-generated method stub
    27.  
    28. 				// 负数   0  正数 三种值
    29. 				System.out.println(o1.compareTo(o2));
    30.             //调佣实体中编写好的方法
    31. 				return o2.compareTo(o1);
    32. 			}
    33.  
    34.  
    35. 		});
    36. 		treeMap.put("1", new Student(1, "zs"));
    37. 		treeMap.put("2", new Student(3, "ls"));
    38. 		treeMap.put("3", new Student(2, "ww"));
    39. 		treeMap.put("4", new Student(4, "zl"));
    40. 	}
    41. 	
    42. 	@Test
    43. 	public void demo1() {
    44. 		treeMap.forEach((key, val) -> System.out.println(key + ":" + val));
    45. 	}
    46. 	
    47. 	@Test
    48. 	public void linkedHashMap() {
    49. 		
    50. 		Map<String, String> linkedHashMap = new LinkedHashMap<>();
    51.         linkedHashMap.put("name1", "josan1");
    52.         linkedHashMap.put("name2", "josan2");
    53.         linkedHashMap.put("name3", "josan3");
    54.         Set<Entry<String, String>> set = linkedHashMap.entrySet();
    55.         Iterator<Entry<String, String>> iterator = set.iterator();
    56.         while(iterator.hasNext()) {
    57.             Entry entry = iterator.next();
    58.             String key = (String) entry.getKey();
    59.             String value = (String) entry.getValue();
    60.             System.out.println("key:" + key + ",value:" + value);
    61.         }
    62. 	}
    63.  
    64. }

    Student类

    1. package com.zking.jee02.model;
    2.  
    3. import java.io.Serializable;
    4.  
    5. public class Student implements Serializable, Comparable<Student> {
    6. 	
    7. 	private Integer id;
    8. 	
    9. 	private String name;
    10.  
    11. 	public Integer getId() {
    12. 		return id;
    13. 	}
    14.  
    15. 	public void setId(Integer id) {
    16. 		this.id = id;
    17. 	}
    18.  
    19. 	public String getName() {
    20. 		return name;
    21. 	}
    22.  
    23. 	public void setName(String name) {
    24. 		this.name = name;
    25. 	}
    26.  
    27. 	public Student(Integer id, String name) {
    28. 		super();
    29. 		this.id = id;
    30. 		this.name = name;
    31. 	}
    32. 	
    33. 	public Student() {
    34. 		
    35. 	}
    36.  
    37. 	@Override
    38. 	public String toString() {
    39. 		return "Student [id=" + id + ", name=" + name + "]";
    40. 	}
    41.  
    42. 	
    43. 	@Override
    44. 	public int hashCode() {
    45. 		final int prime = 31;
    46. 		int result = 1;
    47. 		result = prime * result + ((id == null) ? 0 : id.hashCode());
    48. 		result = prime * result + ((name == null) ? 0 : name.hashCode());
    49. 		return result;
    50. 	}
    51.  
    52. 	@Override
    53. 	public boolean equals(Object obj) {
    54. 		if (this == obj)
    55. 			return true;
    56. 		if (obj == null)
    57. 			return false;
    58. 		if (getClass() != obj.getClass())
    59. 			return false;
    60. 		Student other = (Student) obj;
    61. 		if (id == null) {
    62. 			if (other.id != null)
    63. 				return false;
    64. 		} else if (!id.equals(other.id))
    65. 			return false;
    66. 		if (name == null) {
    67. 			if (other.name != null)
    68. 				return false;
    69. 		} else if (!name.equals(other.name))
    70. 			return false;
    71. 		return true;
    72. 	}
    73.  
    74. 	
    75. 	@Override
    76. 	public int compareTo(Student o) {
    77. 		// TODO Auto-generated method stub
    78. 		// 负数  0 正数
    79. 		if(o.getId() - this.getId()==0){
    80.            return -1;
    81.          }
    82. 		return o.getId() - this.getId();
    83. 	}
    84. 	
    85.  
    86. }

    如果map中没有这个元素那么我们就加入2key这个值 有则没变化

    1. @Test
    2. 	public void demo5() {
    3. 		
    4. 		//如果指定的key值不存在，则加入map
    5. 		if(!map.containsKey("2")) {
    6. 			map.put("2", "RR");
    7. 		}
    8. 		
    9. 		//更简单的方式
    10. 		String val = map.putIfAbsent("2", "RR");
    11. 		
    12. 		System.out.println(map.get("2"));
    13. 		System.out.println(val);
    14. 	}


    Map集合的遍历
    通过键遍历值

    1.  HashMap<Integer,String> map = new HashMap<>();
    2.         map.put(1,"sssss");
    3.         map.put(2,"aaaaa");
    4.         map.put(3,"asdfb");
    5.         for (int i :map.keySet()) {
    6.             String s = map.get(i);
    7.             System.out.println(s);
    8.         }


    通过Iterator迭代器遍历key和value

    1. HashMap<Integer,String> map = new HashMap<>();
    2.         map.put(1,"sssss");
    3.         map.put(2,"aaaaa");
    4.         map.put(3,"asdfb");
    5.        Iterator<Map.Entry<Integer,String>> iterator = map.entrySet().iterator();
    6.         while (iterator.hasNext()){
    7.             Map.Entry<Integer,String> entry = iterator.next();
    8.             System.out.println(entry.getKey()+"+"+entry.getValue());
    9.         }

    通过Entry遍历key和value

    1. HashMap<Integer,String> map = new HashMap<>();
    2.         map.put(1,"sssss");
    3.         map.put(2,"aaaaa");
    4.         map.put(3,"asdfb");
    5.         for (Map.Entry<Integer,String> entry:map.entrySet()) {
    6.             System.out.println(entry.getKey()+"+"+entry.getValue());
    7. }

    通过map.values()遍历所有值

    1.  HashMap<Integer,String> map = new HashMap<>();
    2.         map.put(1,"sssss");
    3.         map.put(2,"aaaaa");
    4.         map.put(3,"asdfb");
    5.         for (String s:map.values()) {
    6.             System.out.println(s);
    7.         }


     

  • 相关阅读:
    Python系列：彩色日志详解
    考勤管理系统
    1048 Find Coins
    guava缓存使用不当导致的FullGC
    趣谈网络协议_1
    几个友好Java代码习惯建议
    JavaWep对象的使用
    Centos7下zabbix安装与部署，设置中文（保姆级图文）【网络工程】
    书生·浦语大模型全链路开源体系-笔记&作业4
    git everything up-to-date解决方法
  • 原文地址：https://blog.csdn.net/qq_62898618/article/details/125525712