容器 从上图要记住，set和list都继承自Collection，所以set和list的方法基本一致。而map则又是一个单独的接口；
数组
数组的优势：是一种简单的线性序列，可以快速地访问数组元素，效率高。如果从效率和类型检查的角度讲，数组是最好的。
数组的劣势：不灵活。容量需要事先定义好，不能随着需求的变化而扩容。比如：我们在一个用户管理系统中，要把今天注册的所有用户取出来，那么这样的用户有多少个?我们在写程序时是无法确定的。因此，在这里就不能使用数组。
范型 如果一个餐厅的大厨把羊肉，鱼肉都放在一个容器里面，那么取的时候就很麻烦 把鱼肉和羊肉分开放在一个容器里面，取的时候就很方便
范型就是一个数据类型(可以拿基本数据类型做比较，但是范型不仅支持基本数据类型，还支持引用型)
public class testString { public static void main(String[] args) throws ParseException, IOException { MyCollection<String> mc = new MyCollection(); mc.set("佘野无敌大帅哥",0); System.out.println(mc.get(1)); } } class MyCollection<E>{ Object[] objs = new Object[5]; public void set(E e,int index){ objs[index] = e; } public E get(int index){ return (E)objs[index]; } }List
List是有序、可重复的容器 有序：List中每个元素都有索引标记。可以根据元素的索引标记(在List中的位置)访问元素，从而精确控制这些元素。 可重复：List允许加入重复的元素。更确切地讲，List通常允许满足 e1.equals(e2) 的元素重复加入容器。
List接口常用的实现类有3个：ArrayList(数组)、LinkedList(链表)和Vector(数组----线程安全)
(1) 数组：占用空间连续。 寻址容易，查询速度快。但是，增加和删除效率非常低。
(2) 链表：占用空间不连续。 寻址困难，查询速度慢。但是，增加和删除效率非常高。
ArrayList特点和底层实现
ArrayList底层是用数组实现的存储。 特点：查询效率高，增删效率低，线程不安全。我们一般使用它
我们知道，数组长度是有限的，而ArrayList是可以存放任意数量的对象，长度不受限制，那么它是怎么实现的呢?本质上就是通过定义新的更大的数组，将旧数组中的内容拷贝到新数组，来实现扩容。 ArrayList的Object数组初始化长度为10，如果我们存储满了这个数组，需要存储第11个对象，就会定义新的长度更大的数组，并将原数组内容和新的元素一起加入到新数组中，源码如下：
自写ArrayList
/** * @author Sheye * @date 2019-10-30 21:25 * 1自定义范型 * 2数组扩容 * 3增加set和get方法 * 4数组边界的检查 * 5增加remove方法 */ public class SheyeArrayList<E> { private Object[] elementData; private int size; private static final int DFAULT_CAPACITY = 10; public SheyeArrayList(){ elementData=new Object[DFAULT_CAPACITY]; } public SheyeArrayList(int capcity){ if (capcity<=0){ throw new RuntimeException("capacity isn't legitimate:"+capcity); } elementData=new Object[capcity]; } //list的长度 public int size(){ return size; } //list是否为空 public boolean isEmpty(){ return size==0?true:false; } //添加元素 public void add(E obj){ //什么时候扩容 if (size==elementData.length){ //扩容操作,>>1为/2,<<为乘2 Object[] newArray = new Object[elementData.length+(elementData.length>>1)]; System.arraycopy(elementData,0,newArray,0,elementData.length); //newArray指向elementData，旧数组被回收 elementData=newArray; } elementData[size++]=obj; } //取值 public E get(int index){ rangeCheck(index); return (E)elementData[index]; } //设置元素 public void set(int index,E element){ rangeCheck(index); elementData[index]=element; } //移除元素 public void remove(E element){ //element.将他所有的元素进行比较，删除找到的第一个元素 for (int i = 0; i <size ; i++) { //get为上面的get方法 if (element.equals(get(i))){ remove(i); } } } public void remove(int index){ //abcdefgh //abcefgh int numMoved = elementData.length-index-1; if (numMoved>0){ System.arraycopy(elementData,index+1,elementData,index,numMoved); //elementData[size-1]=null; //size--; //这里如果没有以上两步,删除的结果将会是abcefghh,上两行和下两行代码出现重复,统一用elementData[--size]=null表示 } //elementData[size-1]=null; //size--; elementData[--size]=null; } //判断是否超出索引 public void rangeCheck(int index){ //判断索引是否合法 if (index<0||index>size-1){ //不合法 throw new RuntimeException("index isn't legitimate:"+index); } } public String toString(){ StringBuilder sb = new StringBuilder(); sb.append("["); for (int i = 0; i <size ; i++) { sb.append(elementData[i]+","); } sb.setCharAt(sb.length()-1,']'); return sb.toString(); } public static void main(String[] args) { SheyeArrayList s1 = new SheyeArrayList(); for (int i = 0; i <20 ; i++) { s1.add("sheye" + i); } s1.set(10,"ddd"); System.out.println("s1 = " + s1); System.out.println("s1.get(10) = " + s1.get(10)); s1.remove("sheye3"); System.out.println("s1 = " + s1); System.out.println("s1.size = " + s1.size); System.out.println("s1.isEmpty() = " + s1.isEmpty()); } }运行结果:
s1 = [sheye0,sheye1,sheye2,sheye3,sheye4,sheye5,sheye6,sheye7,sheye8,sheye9,ddd,sheye11,sheye12,sheye13,sheye14,sheye15,sheye16,sheye17,sheye18,sheye19] s1.get(10) = ddd s1 = [sheye0,sheye1,sheye2,sheye4,sheye5,sheye6,sheye7,sheye8,sheye9,ddd,sheye11,sheye12,sheye13,sheye14,sheye15,sheye16,sheye17,sheye18,sheye19] s1.size = 19 s1.isEmpty() = falseLinkedList特点和底层实现
LinkedList底层用双向链表实现的存储。特点：查询效率低，增删效率高，线程不安全。
双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。 所以，从双向链表中的任意一个节点开始，都可以很方便地找到所有节点。
自写LinkedList
Node类:(本质跟c语言中的结构体(Struct)一样,c中建立链表也是定义如下结构体)
/** * @author Sheye * @date 2019-11-07 21:25 */ public class Node { Node previous; //上一个结点 Node next; //下一个结点 Object element; //元素数据 public Node(Node previous, Node next, Object element) { this.previous = previous; this.next = next; this.element = element; } public Node(Object element) { this.element = element; } }LinkedList类:
/** * @author Sheye * @date 2019-11-07 21:33 * 1自定义一个链表 * 2添加一个add方法 * 3添加一个get方法 * 4添加一个remove方法 * 5插入结点 * 6增加范型 * 7添加size * 8添加是否为空 */ public class LinkedList<E> { private Node first; private Node last; private int size; //给出index找出当前结点 public Node getNode(int index){ //Node tmp = first; Node tmp = null; //分割成两端小于mid的从头开始，大于mid的从尾开始,二分搜索应该效率更高 if (index<=(size>>1)){ //size/2 tmp=first; for (int i = 0; i <index ; i++) { tmp=tmp.next; } } else { tmp=last; for (int i = size-1; i > index; i--) { tmp=tmp.previous; //循环链表第一个的前一个就是尾端(刚开始是这么理解，后来发现add方法中其实定义的是单链表) } } return tmp; } //判断索引是否越界 public void rangeCheck(int index){ if (index<0||index>size-1){ throw new RuntimeException("Index out of bounds:"+index); } } //list的长度 public int size(){ return size; } //list是否为空 public boolean isEmpty(){ //如果第一个结点为空，那么此链表为空 return first==null?true:false; } //插入 public void insert(int index,E element){ rangeCheck(index); Node newNode= new Node(element); Node tmp = getNode(index); if (tmp!=null){ Node up = tmp.previous; up.next=newNode; newNode.previous=up; newNode.next=tmp; tmp.previous=newNode; size++; //原视频中是没有此句话的--->如果不加，调用size方法时不会显示正确值 } } //[] //[a,b,c,e,f]--->取出第二个就是first.next.next //取出元素 public E get(int index){ rangeCheck(index); Node tmp =getNode(index); return tmp!=null?(E)tmp.element:null; //以防发生空指针 } public void remove(int index){ rangeCheck(index); Node tmp = getNode(index); if (tmp!=null){ Node up = tmp.previous; Node down = tmp.next; if (up!=null){ up.next=down; } if (down!=null){ down.previous=up; } if (index==0){ //如果是第一个，将第一个的下一个作为第一个，等于删除原来的最后一个结点 first=down; } if (index==size-1){ //如果是最后一个，将最后一个的上一个作为最后一个，等于删除原来的最后一个结点 last=down; } size--; } } //添加元素 public void add(E element){ Node node = new Node(element); //如果第一个结点为空,第一次添加数据 if (first==null){ node.previous=null; node.next=null; first=node; last=node; }else{ //[a,b]中添加c--->[a,b,c]，当前结点c的上一个是原来[a,b]的最后一个，c的下一个为空 node.previous=last; node.next=null; //将原本[a,b]中的last--->b的next指向当前结点c.c成为最后一个结点 last.next=node; last=node; } size++; } public String toString(){ StringBuffer sb = new StringBuffer("["); Node tmp=first; while (tmp!=null){ //System.out.println("tmp.element = " + tmp.element); sb.append(tmp.element+","); tmp=tmp.next; } //sb.append("]");--->[a,b,c,] sb.setCharAt(sb.length()-1,']'); return sb.toString(); //"aa"; } public static void main(String[] args) { LinkedList<String> list = new LinkedList<>(); list.add("a"); list.add("b"); list.add("c"); list.add("d"); list.add("e"); /** * toString方法的执行顺序，先执行方法里面的System.out.println * 再执行System.out.println("bb"+list)--->()里面的""内容 * 在最后执行return里面的语句 */ System.out.println(list); //如果无法理解类中有本类对象可以debug此行 System.out.println("list.get(4) = " + list.get(4)); list.remove(0); System.out.println(list); list.remove(3); System.out.println(list); list.insert(1,"嘿嘿嘿"); System.out.println(list); System.out.println(list.get(1)); System.out.println("list.size = " + list.size()); System.out.println("list.isEmpty = " + list.isEmpty()); } }运行结果:
[a,b,c,d,e] list.get(4) = e [b,c,d,e] [b,c,d] [b,嘿嘿嘿,c,d] 嘿嘿嘿 list.size = 4 list.size = falsevector:
Vector底层是用数组实现的List，相关的方法都加了同步检查，因此“线程安全,效率低”。 比如，indexOf方法就增加了synchronized同步标记。
vector的每一个方法基本上都加上了锁，多线程访问同一资源的时候，为防止资源数据的紊乱(比较像读者与写者问题，当读者进入一间教室，那么会在教室门口贴上读者禁止入内，当读者全部离开教室，写者才能进入，并在门口贴上读者禁止入内----防止数据紊乱)，而有锁的线程才能对数据进行访问。
Map接口:
现实生活中，我们经常需要成对存储某些信息。比如，我们使用的微信，一个手机号只能对应一个微信账户。这就是一种成对存储的关系。
Map就是用来存储“键(key)-值(value) 对”的。 Map类中存储的“键值对”通过键来标识，所以“键对象”不能重复。 Map 接口的实现类有HashMap、TreeMap、HashTable、Properties等。 import java.util.HashMap; import java.util.Map; /** * @author Sheye * @date 2019-11-08 20:11 */ public class map { public static void main(String[] args) { Map<Integer,String> m = new HashMap<>(); m.put(1,"one"); m.put(2,"two"); m.put(3,"three"); System.out.println("m = " + m); //map中键不能重复！如果重复（是否重复是根据equals方法来判断），则新的覆盖旧的 m.put(2,"二"); System.out.println("m = " + m); } }运行结果:
m = {1=one, 2=two, 3=three} m = {1=one, 2=二, 3=three}HashMap:
HashMap底层实现采用了哈希表，这是一种非常重要的数据结构。对于我们以后理解很多技术都非常有帮助(比如：redis数据库的核心技术和HashMap一样)，因此，非常有必要让大家理解。
数据结构中由数组和链表来实现对数据的存储，他们各有特点。 (1) 数组：占用空间连续。 寻址容易，查询速度快。但是，增加和删除效率非常低。 (2) 链表：占用空间不连续。 寻址困难，查询速度慢。但是，增加和删除效率非常高。 那么，我们能不能结合数组和链表的优点(即查询快，增删效率也高)呢? 答案就是“哈希表”。 哈希表的本质就是“数组+链表”。一个Entry对象存储了：
1. key：键对象 value：值对象 2. next:下一个节点 3. hash: 键对象的hash值 显然每一个Entry对象就是一个单向链表结构，我们使用图形表示一个Entry对象的典型示意：Entry[]数组的结构(这也是HashMap的结构)：
HashMap如何存储数据。此处的核心是如何产生hash值，该值用来对应数组的存储位置。 假设m1为put(1,“aa”),m2为put(2,“bb”)，计算m1的key对象的hash值(不同于hashcode)为15，则放入table数组(上图中的entry[]为table数组中存有entry对象—>形成的单链表)中下标为15的位置，计算m2的key对象的hash值(不同于hashcode)也为15的话,就以单链表的形式在m1后面
散列算法将hashcode计算出hash值，将entry散列到table数组中，使单链表尽量分配得均匀.
(1) 获得key对象的hashcode 首先调用key对象的hashcode()方法，获得hashcode。 (2) 根据hashcode计算出hash值(要求在[0, 数组长度-1]区间) hashcode是一个整数，我们需要将它转化成[0, 数组长度-1]的范围。我们要求转化后的hash值尽量均匀地分布在[0,数组长度-1]这个区间，减少“hash冲突” i. 一种极端简单和低下的算法是： hash值 = hashcode/hashcode; 也就是说，hash值总是1。意味着，键值对对象都会存储到数组索引1位置，这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash冲突”，HashMap也退化成了一个“链表”。 ii. 一种简单和常用的算法是(相除取余算法)： hash值 = hashcode%数组长度 这种算法可以让hash值均匀的分布在[0,数组长度-1]的区间。 早期的HashTable就是采用这种算法。但是，这种算法由于使用了“除法”，效率低下。JDK后来改进了算法。首先约定数组长度必须为2的整数幂，这样采用位运算即可实现取余的效果：hash值 = hashcode&(数组长度-1)。 (3) 生成Entry对象 如上所述，一个Entry对象包含4部分：key对象、value对象、hash值、指向下一个Entry对象的引用。我们现在算出了hash值。下一个Entry对象的引用为null。 (4) 将Entry对象放到table数组中 如果本Entry对象对应的数组索引位置还没有放Entry对象，则直接将Entry对象存储进数组;如果对应索引位置已经有Entry对象，则将已有Entry对象的next指向本Entry对象，形成链表。总结如上过程：
当添加一个元素(key-value)时，首先计算key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，就形成了链表，同一个链表上的Hash值是相同的，所以说数组存放的是链表。 JDK8中，当链表长度大于8时，链表就转换为红黑树，这样又大大提高了查找的效率。▪ 取数据过程get(key)
我们需要通过key对象获得“键值对”对象，进而返回value对象。明白了存储数据过程，取数据就比较简单了，参见以下步骤： (1) 获得key的hashcode，通过hash()散列算法得到hash值，进而定位到数组的位置。 (2) 在链表上挨个比较key对象。 调用equals()方法，将key对象和链表上所有节点的key对象进行比较，直到碰到返回true的节点对象为止。 (3) 返回equals()为true的节点对象的value对象。 明白了存取数据的过程，我们再来看一下hashcode()和equals方法的关系： Java中规定，两个内容相同(equals()为true)的对象必须具有相等的hashCode。因为如果equals()为true而两个对象的hashcode不同;那在整个存储过程中就发生了悖论。▪ 扩容问题
HashMap的位桶数组，初始大小为16。实际使用时，显然大小是可变的。如果位桶数组中的元素达到(0.75*数组 length)， 就重新调整数组大小变为原来2倍大小。 扩容很耗时。扩容的本质是定义新的更大的数组，并将旧数组内容挨个拷贝到新数组中。▪ JDK8将链表在大于8情况下变为红黑二叉树
JDK8中，HashMap在存储一个元素时，当对应链表长度大于8时，链表就转换为红黑树，这样又大大提高了查找的效率。手工实现HashMap:
Entry类:
/** * @author Sheye * @date 2019-11-08 22:59 */ public class Entry<K,V> { int hash; K key; V value; Entry next; }MyMap类:
import java.util.HashMap; import java.util.Map; /** * @author Sheye * @date 2019-11-08 20:11 * 1实现put方法 * 2增加toString方法 * 3增加get方法 */ public class MyMap<K,V> { Entry[] table; //位桶数组，bucket Array int size; //存放键值对的个数 int length; //记录table数组被占的个数，当等于table.length*0.75，进行扩容 private final static int DEFAULT_SIZE=16; public MyMap() { table = new Entry[DEFAULT_SIZE]; //长度一般定义为2的整数幂 } public V get(K key){ int hash = hashValue(key.hashCode(),table.length); V value=null; if (table[hash]!=null){ Entry tmp = table[hash]; while (tmp!=null){ if (key.equals(tmp.key)){ value=(V)tmp.value; break; }else { tmp=tmp.next; } } } return value; } //元素放入hashmap public void put(K key,V value){ //数组扩容 if (length==table.length*0.75){ Entry[] newArray = new Entry[table.length*2]; System.arraycopy(table,0,newArray,0,table.length); //newArray指向table，旧数组被回收 table=newArray; } Entry newEntry = new Entry(); newEntry.hash=hashValue(key.hashCode(),table.length); newEntry.key=key; newEntry.value=value; newEntry.next=null; Entry tmp = table[newEntry.hash]; Entry iterLast=null; //正在遍历的最后一个元素 boolean keyRepeat=false; if (tmp==null){ //此处数组元素为空，则直接将新结点放进去 table[newEntry.hash]=newEntry; length++; size++; //第一个进数组的entry }else{ //此处数组元素为空,则遍历对应链表 while (tmp!=null){ //判断key如果重复,则覆盖 if (tmp.key.equals(key)){ keyRepeat=true; tmp.value=value; //只是覆盖value，其他值保持不变 break; //如果出现重复,将退出链表的遍历,如果不退出，当前结点始终是！null。死循环 }else { //key不重复,则遍历下一个 iterLast=tmp; //最后一个 tmp=tmp.next; } } if (!keyRepeat){ //一开始没有加此行，那么break之后，iterLast是为null的，报空指针异常 iterLast.next=newEntry; //每添加一个entry之前的那个结点其实都是最后一个，将新结点赋值给最后一个结点的next，形成单链表 size++; //单链表后的entry } } } public void remove(K key){ //此处本想实现删除，但是单链表已知上一结点可以删除下一节点，知道本结点的下一结点，怎么删除本结点，此方法直接跳过即可 int hash = hashValue(key.hashCode(),table.length); Entry tmp = table[hash]; Entry removeEntry = null; if (tmp!=null){ //删除的链表的第一个 //删除的链表中的后面中的一个 while(tmp!=null){ if (tmp.key.equals(key)){ removeEntry=tmp.next; tmp.hash=removeEntry.hash; tmp.key=removeEntry.key; tmp.value=removeEntry.value; tmp=tmp.next; break; }else { tmp=tmp.next; } } } } //将hashcode计算为hash值 public int hashValue(int v,int length){ //System.out.println(" hash value----" + (v&(length-1))); //效率高 //System.out.println(" hash value----" + (v%(length-1))); //效率低 return v&(length-1); } public String toString(){ //{10:aa,20:bb} StringBuffer sb = new StringBuffer("{"); //遍历bucket数组 for (int i = 0; i <table.length ; i++) { Entry tmp = table[i]; //遍历单链表 while(tmp!=null){ sb.append(tmp.key+":"+tmp.value+","); tmp=tmp.next; } } sb.setCharAt(sb.length()-1,'}'); return sb.toString(); } public static void main(String[] args) { MyMap<Integer,String> m = new MyMap<>(); //entry为什么不加<Integer,String>的原因是，entry中没有方法，没有返回值，加与不加都一样，不加就相当于Object // for (int i = 0; i <20 ; i++) { // m.put(i,"aa"); // } m.put(1,"aa"); m.put(2,"bb"); m.put(3,"cc"); System.out.println("m = " + m); System.out.println("m.get(1)= " + m.get(3)); //m.remove(1); //System.out.println("m = " + m); //System.out.println("((Object)55).hashCode() = " + ((Integer)55).hashCode()); 整数的hashcode就等于它本身 //System.out.println("\"String\".hashCode() = " + "String".hashCode()); } }运行结果:
m = {1:aa,2:bb,3:cc} m.get(1)= ccTreeMap的使用和底层实现（用于排序）：
TreeMap是红黑二叉树的典型实现
import java.util.HashMap; import java.util.Map; import java.util.TreeMap; /** * @author Sheye * @date 2019-11-10 12:19 */ public class TestTreeMap { public static void main(String[] args) { Map<Integer,String> hm = new HashMap<>(); hm.put(20,"aa"); hm.put(3,"bb"); hm.put(6,"cc"); //传统的hashmap乱序输出 for (Integer key:hm.keySet() ) { System.out.println(key+"----"+hm.get(key)); } Map<Integer,String> tm = new TreeMap<>(); tm.put(20,"aa"); tm.put(3,"bb"); tm.put(6,"cc"); System.out.println("-------------------------------------- " ); //treemap按照key递增的方式排序 for (Integer key:tm.keySet() ) { System.out.println(key+"----"+tm.get(key)); } Map<Employee,String> tm1 = new TreeMap<>(); tm1.put(new Employee(100,"张三",50000),"张三是一个好小伙"); tm1.put(new Employee(200,"李四",5000),"李四是一个好小伙"); tm1.put(new Employee(150,"王五",6000),"王五是一个好小伙"); tm1.put(new Employee(50,"赵六",6000),"赵六是一个好小伙"); System.out.println("-------------------------------------- " ); //treemap按照key递增的方式排序 for (Employee key:tm1.keySet() ) { System.out.println(key+"----"+tm1.get(key)); } } } //Employee与Employee进行比较 class Employee implements Comparable<Employee>{ int id; String name; double salary; public Employee(int id, String name, double salary) { this.id = id; this.name = name; this.salary = salary; } //按照salary递增的顺序排序，如果相等。就按照id递增的顺序排序 //如果想要进行降序，把1换成-1，-1换成1即可 /** * 将此对象与指定对象进行比较 * 我的理解:现在也不好追究底层，比如第一数为当前对象，第二个数为比较对象， * 当第一个数大于第二个数，我们设置返回值1（大于）,保持不变，形成升序 * 当第一个数大于第二个数，我们设置返回值-1(小于)，将大数置后，形成降序 */ @Override public int compareTo(Employee o) { //负数：小于，0：等于，整数：大于 if (this.salary>o.salary){ return 1; }else if(this.salary<o.salary){ return -1; }else { if (this.id>o.id){ return 1; }else if (this.id<o.id){ return -1; }else { return 0; } } } @Override public String toString() { return "Employee{" + "id=" + id + ", name='" + name + '\'' + ", salary=" + salary + '}'; } }运行结果:
3----bb 20----aa 6----cc -------------------------------------- 3----bb 6----cc 20----aa -------------------------------------- Employee{id=200, name='李四', salary=5000.0}----李四是一个好小伙 Employee{id=50, name='赵六', salary=6000.0}----赵六是一个好小伙 Employee{id=150, name='王五', salary=6000.0}----王五是一个好小伙 Employee{id=100, name='张三', salary=50000.0}----张三是一个好小伙HashTable(用法与hashmap相同):
HashMap与HashTable的区别
1. HashMap: 线程不安全，效率高。允许key或value为null。 2. HashTable: 线程安全，效率低。不允许key或value为null。Set(接口):
Set接口继承自Collection，Set接口中没有新增方法，方法和Collection保持完全一致。我们在前面通过List学习的方法，在Set中仍然适用。
Set容器特点：无序、不可重复（因为hashset作为hashmap的key存在，所以不可重复）。无序指Set中的元素没有索引，我们只能遍历查找;不可重复指不允许加入重复的元素。更确切地讲，新元素如果和Set中某个元素通过equals()方法对比为true，则不能加入;甚至，Set中也只能放入一个null元素，不能多个。
Set常用的实现类有：HashSet、TreeSet等，我们一般使用HashSetHashSet底层实现：
HashSet是采用哈希算法实现，底层实际是用HashMap实现的(HashSet本质就是一个简化版的HashMap)，因此，查询效率和增删效率都比较高 我们发现里面有个map属性，这就是HashSet的核心秘密。我们再看add()方法，发现增加一个元素说白了就是在map中增加一个键值对，键对象就是这个元素，值对象是名为PRESENT的Object对象。说白了，就是“往set中加入元素，本质就是把这个元素作为key加入到了内部的map中”
手工实现hashset:
import java.util.HashMap; /** * @author Sheye * @date 2019-11-10 13:34 */ public class MyHashSet { HashMap map; private static final Object PRESENT=new Object(); public MyHashSet() { map=new HashMap(); } public void add(Object o){ map.put(o,PRESENT); } public int size(){ return map.size(); } @Override public String toString() { StringBuilder sb = new StringBuilder("["); for (Object key: map.keySet()) { sb.append(key+","); } sb.setCharAt(sb.length()-1,']'); return sb.toString(); } public static void main(String[] args) { MyHashSet mhs = new MyHashSet(); mhs.add(1); mhs.add(2); mhs.add(3); System.out.println("mhs = " + mhs); } }运行结果:
mhs = [1,2,3]TreeSet的使用和底层实现：
TreeSet底层实际是用TreeMap实现的，内部维持了一个简化版的TreeMap，通过key来存储Set的元素。 TreeSet内部需要对存储的元素进行排序，因此，我们对应的类需要实现Comparable接口。这样，才能根据compareTo()方法比较对象之间的大小，才能进行内部排序。
import java.util.Set; import java.util.TreeSet; /** * @author Sheye * @date 2019-11-10 14:44 */ public class TestTreeSet { public static void main(String[] args) { Set<Integer> ts = new TreeSet<>(); ts.add(300); ts.add(200); ts.add(500); //递增的顺序 for (Integer key: ts) { System.out.println("key = " + key); } System.out.println("------------------------------------------------------" ); Set<Emp> ts1 = new TreeSet<>(); ts1.add(new Emp(3,"张三",3000)); ts1.add(new Emp(5,"李四",1000)); ts1.add(new Emp(1,"王五",4000)); ts1.add(new Emp(4,"赵六",2000)); //递增的顺序 for (Emp key: ts1) { System.out.println("key = " + key); } } } class Emp implements Comparable<Emp>{ int id; String name; double salary; public Emp(int id, String name, double salary) { this.id = id; this.name = name; this.salary = salary; } @Override public int compareTo(Emp o) { if (this.salary>o.salary){ return 1; }else if(this.salary<o.salary){ return -1; }else { if (this.id>o.id){ return 1; }else if (this.id<o.id){ return -1; }else { return 0; } } } @Override public String toString() { return "Employee{" + "id=" + id + ", name='" + name + '\'' + ", salary=" + salary + '}'; } }运行结果:
key = 200 key = 300 key = 500 ------------------------------------------------------ key = Employee{id=5, name='李四', salary=1000.0} key = Employee{id=4, name='赵六', salary=2000.0} key = Employee{id=3, name='张三', salary=3000.0} key = Employee{id=1, name='王五', salary=4000.0}使用Iterator迭代器遍历容器元素(List/Set/Map)：
import java.util.*; /** * @author Sheye * @date 2019-11-10 14:58 */ public class TestIterator { public static void main(String[] args) { testIteratorList(); System.out.println("-----------------------------------------我是一条分界线----------------------------------------- " ); testIteratorSet(); System.out.println("-----------------------------------------我是一条分界线----------------------------------------- " ); testIteratorMap(); } public static void testIteratorList(){ List<String> list = new ArrayList<>(); list.add("aa"); list.add("bb"); list.add("cc"); //创建一个调用list本身的方法创建一个迭代器对象 for (Iterator<String> iter = list.iterator();iter.hasNext();){ String tmp = iter.next(); System.out.println("tmp = " + tmp); } } public static void testIteratorSet(){ Set<String> set = new HashSet<>(); set.add("aa"); set.add("bb"); set.add("cc"); //创建一个调用set本身的方法创建一个迭代器对象 for (Iterator<String> iter = set.iterator();iter.hasNext();){ String tmp = iter.next(); System.out.println("tmp = " + tmp); } } public static void testIteratorMap(){ Map<Integer,String> map = new HashMap<>(); map.put(1,"aa"); map.put(2,"bb"); map.put(3,"cc"); //第一种方法通过entry结点进行迭代 Set<Entry<Integer,String>> ss = map.entrySet(); for (Iterator<Entry<Integer,String>> iter = ss.iterator(); iter.hasNext();){ Entry<Integer,String> e = iter.next(); System.out.println(e.getKey+ "--" + e.getValue); //运行时总是在报错，故没有结果 } System.out.println("-----------------------------------------我是一条分界线----------------------------------------- " ); //第二种方法，通过key进行迭代 Set<Integer> ss1 = map.keySet(); for (Iterator<Integer> iter = ss1.iterator();iter.hasNext();){ int key = iter.next(); System.out.println(key+"---------"+map.get(key) ); } } }运行结果:
tmp = aa tmp = bb tmp = cc -----------------------------------------我是一条分界线----------------------------------------- tmp = aa tmp = bb tmp = cc -----------------------------------------我是一条分界线----------------------------------------- -----------------------------------------我是一条分界线----------------------------------------- 1---------aa 2---------bb 3---------ccforeach的迭代就不多简绍
Collections工具类:
类 java.util.Collections 提供了对Set、List、Map进行排序、填充、查找元素的辅助方法。
1. void sort(List) //对List容器内的元素排序，排序的规则是按照升序进行排序。 2. void shuffle(List) //对List容器内的元素进行随机排列。 3. void reverse(List) //对List容器内的元素进行逆续排列 。 4. void fill(List, Object) //用一个特定的对象重写整个List容器。 5. int binarySearch(List, Object)//对于顺序的List容器，采用折半查找的方法查找特定对象。