J2EE从入门到入土02.Set及Map集合解析

set集合

HashSet

元素新增

TreeSet

set集合

set集合主要看一下两个：HashSet、TreeSet

HashSet

特点是：

特点：无序，不重复
扩容：初始容量16，负载因子0.75，扩容增量1倍

示例：new HashSet<>(20, 0.5f);

它存储唯一元素并允许空值
依据对象的hashcode来确定该元素是否存在
由HashMap支持
不保持插入顺序
非线程安全

HashSet底层就是用HashMap实现的，也就是非线程安全.


 private transient HashMap<E,Object> map;
 //构造一个初始容量16，加载因子是0.75的HashMap
public HashSet() {
    map = new HashMap<>();
}

既然是用HashMap实现的，那么问题来了，Set存的只是一个对象，而HashMap存的是<K,V>键值对，怎么用HashMap作为Set的底层呢？

元素新增


private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

可以看到，HashSet只使用了HashMap的key，而值PRESENT是一个对象常量。这也是为什么Set里面的元素都是唯一的。

返回是map.put(e, PRESENT)==null表达式，HashMap在新增值的时候如果已有则返回旧值，反之，返回null，所以这也是Set判断重复添加值的时候是否添加成功。

TreeSet

特点：是一个包含有序的且没有重复元素的集合
作用是提供有序的Set集合，自然排序或者根据提供的Comparator进行排序，可以在对象出重写比较器，也要重写hashCode方法可以根据自己需求来比较排序，也可以在方法内新建对象来new一个比较器，在对象里面需要重写hashCodee方法


public class Student implements Comparable<Student>{
	
	private Integer sid;
	
	private String sname;
	
	private int age;
	
	
 
	public Student(Integer sid, String sname, int age) {
		super();
		this.sid = sid;
		this.sname = sname;
		this.age = age;
	}
 
	public Integer getSid() {
		return sid;
	}
 
	public void setSid(Integer sid) {
		this.sid = sid;
	}
 
	public String getSname() {
		return sname;
	}
 
	public void setSname(String sname) {
		this.sname = sname;
	}
 
	public int getAge() {
		return age;
	}
 
	public void setAge(int age) {
		this.age = age;
	}
 
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + age;
		result = prime * result + ((sid == null) ? 0 : sid.hashCode());
		result = prime * result + ((sname == null) ? 0 : sname.hashCode());
		return result;
	}
 
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Student other = (Student) obj;
		if (age != other.age)
			return false;
		if (sid == null) {
			if (other.sid != null)
				return false;
		} else if (!sid.equals(other.sid))
			return false;
		if (sname == null) {
			if (other.sname != null)
				return false;
		} else if (!sname.equals(other.sname))
			return false;
		return true;
	}
 
	@Override
	public String toString() {
		return "Student [sid=" + sid + ", sname=" + sname + ", age=" + age + "]";
	}
 
	@Override
	public int compareTo(Student o) {
		if(this.getAge()-o.getAge()==0) {
			return this.getSid()-o.getSid();
		}
		return this.getAge() - o.getAge();
	}

TreeSet的底层是TreeMap，而TreeMap底层数据结构是红黑树。


public TreeSet() {
      this(new TreeMap<E,Object>());
  }

TreeMap的节点结构如下：


class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
 }

红黑树的起源，自然是二叉查找树了，这种树结构从根节点开始，左子节点小于它，右子节点大于它。每个节点都符合这个特性，所以易于查找，是一种很好的数据结构

红黑树

注：红黑数是平衡二叉树的一种，插入时遵循二叉树“左右”定律：

该父节点的左子节点：为小于父节点中且子树中最接近父节点值得数。

该父节点的右子节点：为大于父节点中且子树中最接近父节点值得数。

Map

特点：

无序，键值对，键不能重复，值可以重复，
键重复则覆盖，没有继承Collection接口

遍历方式：

先获取所有键的Set集合，再遍历（通过键获取值）
取出保存所有Entry的Set,再遍历此Set即可

扩容：初始容量16，负载因子0.75，扩容增量1倍

常用类型

HashMap ConcurrentHashMap TreeMap LinkedHashMap

HashMap

线程不安全，最常用，速度快
内部采用数组来存放数据

基本原理

put执行过程

Table数组中的的Node的数据结构

在jdk 1.8之前是这样的一个链表式结构，根据传出的key值来进行哈希值计算，确认放到那个桶内

，如果桶内有重复的值则覆盖掉，没有则把原来的元素往下挤

在jdk 1.8的时候则是改成红黑树结构

流程图中绿色标出的部分为JDK8新增的处理逻辑，目的是在Table[i]中的Node节点数量大于8时，通过红黑树提升查找速度。

根据传出的key值来进行哈希值计算，确认放到那个桶内，如果桶内有重复的值则覆盖掉，则根据根节点来判断值的大小，来分配

ConcurrentHashMap

线程安全，性能高用的比较多，还有一个HashTable这个类方法则是加了一把锁给锁锁住了，运行进程会慢。

源码：读写时会进行上锁，每一个桶也就是每一个节点会上一把锁分段锁，默认16把锁


 final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh; K fk; V fv;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else if (onlyIfAbsent // check first node without acquiring lock
                     && fh == hash
                     && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                     && (fv = f.val) != null)
                return fv;
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key, value);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                        else if (f instanceof ReservationNode)
                            throw new IllegalStateException("Recursive update");
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

TreeMap

key值按一定的顺序排序，基于红黑树，容量无限制，非线程安全，比较常用
添加或获取元素时性能较HashMap慢(因为需求维护内部的红黑树，用于保证key值的顺序)
能比较元素的大小，根据key比较(元素的自然顺序，集合中自定义的比较器也可排序)


private TreeMap<String,Student> treeMap;
	
	@Before
	public void setup() {
		
		treeMap = new TreeMap<String,Student>(new Comparator<String>() {
 
			@Override
			public int compare(String o1, String o2) {
				// 负数   0  正数
				return o1.compareTo(o2);
			}
 
		});
		treeMap.put("1", new Student(5, "小白"));
		treeMap.put("2", new Student(3, "小黑"));
		treeMap.put("3", new Student(2, "小黄"));
		treeMap.put("4", new Student(4, "小明"));
		treeMap.put("3", new Student(1, "小黑"));
		treeMap.put("4", new Student(4, "小明"));
	}

LinkedHashMap

继承HashMap
维护了一个双向链表
LinkedHashMap是有序的，且默认为插入顺序
默认情况下使用entryset获取的集合顺序是与节点的插入顺序(默认是按照插入的顺序进行排列的，最先插入的节点(即最老的节点)为head，最新插入的节点为tail)

注意：有序和无序是描述系统内部状态、客观事物内部各要素以及客观事物之间关系的范畴。有序指系统的组成元素、事物内部诸要素或事物之间的有规则的排列、组合、运动和转化，含结构有序与运动有序；无序则相反，指事物内部诸要素或事物之间、系统内部组成元素之间混乱而无规则的组合、运动和转化，含结构无序和运动无序。有序和无序是世界上存在的两种情形，二者的差异是相对的，世间没有绝对的有序和无序，在有序的事物中存在着破坏其有规则的排列或运动过程的因素，无序的事物中总是包含有有序的因素

相关阅读:
通过股票量化交易券商接口如何减少发生亏损的风险？
作业把dic.txt 导入数据库里
 proguard 混淆jar内容
 【Selenium】Selenium4 Grid
大家都在用MySQL count(*)统计总数，到底有什么问题？
图像处理之理想高通滤波器、巴特沃斯高通滤波器和高斯高通滤波器的matlab简单实现
 计算机组成原理历年考研真题对应知识点（计算机的性能指标）
在window10下python：ocr实战
 论文精读:Swin Transformer V2: Scaling Up Capacity and Resolution
【发布】Photoshop ICO 文件格式插件 3.0
原文地址：https://blog.csdn.net/WZJ278/article/details/125513728