五、Collection子接口之二： Set接口及其实现类
Set接口是Collection的子接口，set接口没有提供额外的方法。 Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个 Set 集合中，则添加操作失败。 Set 判断两个对象是否相同不是使用 == 运算符，而是根据 equals() 方法。
* Set接口的框架
*
* |---Collection接口：单列集合，用来存储一个一个的对象
* |---Set接口：存储无序的、不可重复的数据
* |---HashSet:作为Set接口的主要实现类：线程不安全的：可以存储null值
* |---LinkedHashSet：作为HashSet的子类：遍历其内部数据时，可以按 * 照添加的顺序遍历
* 对于频繁的遍历操作，LinkedHashSet效率高于 * HashSet
* |---TreeSet：可以按照添加对象的指定属性，进行排序
*
* 1.Set接口中没有额外定义新的方法，使用的都是Collection中声明过的方法
*
* 2.要求：向Set中添加的数据，其所在的类一定要重写hashCode()和equals()方法
* 要求：重写的hashCode()和equals()尽可能保持一致性。
一、Set:存储无序的、不可重复的数据
以HashSet为例说明
1.无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的
2.不可重复性：保证添加元素按照equals()判断时，不能返回true，即：相同元素只能添加一个
二、添加数据的过程:以HashSet为例
我们向HashSet中添加元素a，首先调用元素a所在类的hashCode方法，计算元素a的哈希值，
此哈希值接着通过某种算法计算出在HashSet底层数组中存放位置(即为：索引位置)，判断
数组此位置上是否已经有元素：
如果此位置上没有其他元素，则元素a添加成功。--->情况1
如果此位置上有其他元素b(或以链表形式存在的多个元素)，则比较元素a与元素b的哈希值：
如果哈希值不相同，则元素a添加成功。--->情况2
如果哈希值相同，进而需要调用元素a所在类的equals()方法：
equals()返回true，元素a添加失败
equals()返回false，则元素a添加成功。--->情况3
对于添加成功的情况2和情况3而言：元素a与已经存在指定索引位置上数据以链表的方式存储
jdk 7 ：元素a放到数组中，指向原来的元素
jdk 8 ： 原来的元素在数组中，指向元素a
总结：七上八下
HashSet底层：数组+链表的结构。
①HashSet
LinkedHashSet的使用
LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。
优点：对于频繁的遍历操作，LinkedHashSet效率高于HashSet
public class TreeSetTest { /* 1.向TreeSet中添加的数据，要求是相同类的对象 2.两种排序方式：自然排序(实现comparable接口) 和 定制排序(comparator) 3.自然排序中，比较两个对象是否相同的标准为：compareTo()返回0，不再是equals()。 4.定制排序中，比较两个对象是否相同的标准为：compareTo()返回0，不再是equals()。 */ @Test public void test1(){ TreeSet set = new TreeSet(); //不能添加不同类的对象 // set.add(123); // set.add(456); // set.add("AA"); // set.add(new User("Tom",12)); //举例一： // set.add(34); // set.add(-34); // set.add(43); // set.add(11); // set.add(8); //举例二： set.add(new User("Tom",12)); set.add(new User("Jerry",32)); set.add(new User("Jim",2)); set.add(new User("Mike",65)); set.add(new User("Jack",33)); set.add(new User("Jack",56)); Iterator iterator = set.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } } @Test public void test2(){ Comparator com = new Comparator() { //按照年龄从小到大排列 @Override public int compare(Object o1, Object o2) { if(o1 instanceof User && o2 instanceof User){ User u1 = (User)o1; User u2 = (User)o2; return Integer.compare(u1.getAge(),u2.getAge()); }else { throw new RuntimeException("输入的数据类型不匹配"); } } }; TreeSet set = new TreeSet(com); set.add(new User("Tom",12)); set.add(new User("Jerry",32)); set.add(new User("Jim",2)); set.add(new User("Mike",65)); set.add(new User("Jack",33)); set.add(new User("Marry",33)); set.add(new User("Jack",56)); Iterator iterator = set.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } } } public class User implements Comparable{ private String name; private int age; public User() { } public User(String name, int age) { this.name = name; this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public String toString() { return "User{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override public boolean equals(Object o) { System.out.println("User的equals方法"); if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; User user = (User) o; if (age != user.age) return false; return name != null ? name.equals(user.name) : user.name == null; } @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result; } //按照姓名从大到小排序,年龄从小到大排列 @Override public int compareTo(Object o) { if(o instanceof User){ User user = (User)o; // return -this.name.compareTo(user.name); int compare = -this.name.compareTo(user.name); if (compare != 0){ return compare; }else { return Integer.compare(this.age,user.age); } }else { throw new RuntimeException("输入的类型不匹配"); } } }
六、Map接口
一、Map实现类的结构
|----Map：双列数据，存储key-value的数据 ---类似于高中的函数：y = f(x)
|----HashMap:作为Map的主要实现类：线程不安全的，效率高；可以存储null的key-value的数据
|----LinkedHashMap:保证在遍历Map元素时，可以按照添加的顺序实现遍历
原因：在原来的HashMap的基础上，添加了一对指针，指向前一个和后一个元素。
对于频繁的遍历操作，此类执行效率比HashMap高。
|----TreeMap:保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序
底层使用红黑树
|----Hashtable:作为古老的实现类：线程安全的，效率低；不能存储null的key-value的数据
|----Properties:常用来处理配置文件,key和value都是String类型
HashMap的底层： 数据组+链表 (jdk7及之前)
数组+链表+红黑树 (jdk8)
二、Map结构的理解
Map与Collection并列存在。用于保存具有映射关系的数据:key-value
Map 中的 key 和 value 都可以是任何引用类型的数据
Map 中的 key 用Set来存放，不允许重复，即同一个 Map 对象所对应的类，须重写hashCode()和equals()方法
常用String类作为Map的“键”
key 和 value 之间存在单向一对一关系，即通过指定的key总能找到 唯一的、确定的 value Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和 Properties。其中，HashMap是 Map 接口使用频率最高的实现类
三、Map实现类之一：HashMap（ 使用频率最高 的实现类 ）
① HashMap 的存储结构
JDK 7 及以前版本： HashMap 是 数组+链表结构 ( 即为链地址法 )
JDK 8 版本发布以后： HashMap 是 数组+链表+红黑树 实现。
演示图如下：
********************************************************************************************
②HashMap的底层实现原理
以jdk7为例说明：
HashMap map = new HashMap();
在实例化以后，底层创建了长度是16的一维数组Entry[] table。
.....可能已经执行过多次put...
map.put(key1,value1);
首先，计算key1所在类的HashCode()计算key1哈希值，此哈希值经过某种算法计算以后，得到Entry数组中的存放位置。
如果此位置上的数据为空，key1-value1添加成功。 ----情况1
如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在))，比较当前key1和已经存在的一个或多个数据
的哈希值：
如果key1的哈希值跟已经存在的数据的哈希值不同，此时key1-value1添加成功。 ----情况2
如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同，继续比较：调用key11所在类的equals()方法，比较：
如果equals()返回false：此时key1-value1添加成功。 ----情况3
如果equals()返回true：将使用value1替换value2.
补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。形成链表结构时，新添加的key-value对在链表的尾部（七上八下）
在不断的添加过程中，会涉及到扩容问题，当超出临界值(且存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将所有的数据复制过来
jdk8 相较于 jdk7在底层实现方面的不同：
1. new HashMap():底层没有创建：底层没有创建一个长度为16的数组
2. jdk 8底层数组是：Node[],而非Entry[]
3. 首次调用put()方法时，底层创建长度为16的数组
4. jdk7底层结构：数组+链表。
jdk8底层结构：数组+链表+红黑树
当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时
此时此索引位置上的所有数据改为红黑树存储。
③HashMap源码中的重要常量
DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
threshold：扩容的临界值，=容量*填充因子：16*0.75 = 12
TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树：8
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。64
④HashMap的扩容
当 HashMap 中的元素越来越多的时候， hash 冲突的几率也就越来越高，因为数组的 长度是固定的。所以为了提高查询的效率，就要对HashMap 的数组进行扩容，而在 HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算 其在新数组中的位置，并放进去，这就是resize 。
那么 HashMap 什么时候进行扩容呢？
当 HashMap 中的元素个数超过数组大小 loadFactor 时 ， 就 会 进 行 数 组 扩 容 ， loadFactor 的默认值 (DEFAULT_LOAD_FACTOR ) 为 0.75 ，这是一个折中的取值。也就是说，默认情况下，数组大小( DEFAULT_INITIAL_CAPACITY ) 为 16 ，那么当 HashMap 中元素个数 超过16*0.75=12 （这个值就是代码中的 threshold 值，也叫做临界值）的时候，就把 数组的大小扩展为 2*16=32 ，即扩大一倍，然后重新计算每个元素在数组中的位置， 而这是一个非常消耗性能的操作， 所以如果我们已经预知 HashMap 中元素的个数， 那么预设元素的个数能够有效的提高HashMap 的性能。
四、Map实现类之二：LinkedHashMap
LinkedHashMap 是 HashMap 的子类
在 HashMap 存储结构的基础上，使用了一对双向链表来记录添加
元素的顺序
与 LinkedHashSet 类似， LinkedHashMap 可以维护 Map 的迭代
顺序：迭代顺序与 Key-Value 对的插入顺序一致
HashMap 中的内部类： Node
static class Node< K , V > implements Map.Entry< K , V > {
final int hash ;
final K key ;
V value ;
Node< K , V > next ;
}
LinkedHashMap 中的内部类： Entry
static class Entry< K , V > extends HashMap.Node< K , V > {
Entry< K , V > before , after ;
Entry( int hash, K key, V value, Node< K , V > next) {
super (hash, key, value, next);
}
}
五、Map实现类之三：TreeMap
TreeMap 存储 Key-Value 对时，需要根据 key-value 对进行排序。
TreeMap 可以保证所有的 Key-Value 对处于 有序 状态。
TreeSet 底层使用 红黑树 结构存储数据
TreeMap 的 Key 的排序：
自然排序 ： TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有
的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException
定制排序 ：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对
TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现
Comparable 接口
TreeMap 判断 两个 key 相等的标准 ：两个 key 通过 compareTo() 方法或
者 compare() 方法返回 0 。
public class TreeMapTest { //向TreeMap中添加key-value,要求key必须是由同一个类创建的对象 //因为要按照key进行排序：自然排序、定制排序 //自然排序 @Test public void test1(){ TreeMap map = new TreeMap(); User u1 = new User("Tom",23); User u2 = new User("Jerry",32); User u3 = new User("Jack",20); User u4 = new User("Rose",18); map.put(u1,98); map.put(u2,89); map.put(u3,76); map.put(u4,100); Set entrySet = map.entrySet(); Iterator iterator = entrySet.iterator(); while(iterator.hasNext()){ Object o = iterator.next(); Map.Entry entry = (Map.Entry) o; System.out.println(entry.getKey() + "---->" + entry.getValue()); } } //定制排序 @Test public void test2(){ TreeMap map = new TreeMap(new Comparator() { @Override public int compare(Object o1, Object o2) { if (o1 instanceof User && o2 instanceof User){ User u1 = (User) o1; User u2 = (User) o2; return Integer.compare(u1.getAge(),u2.getAge()); } throw new RuntimeException("输入类型不匹配"); } }); User u1 = new User("Tom",23); User u2 = new User("Jerry",32); User u3 = new User("Jack",20); User u4 = new User("Rose",18); map.put(u1,98); map.put(u2,89); map.put(u3,76); map.put(u4,100); Set entrySet = map.entrySet(); Iterator iterator = entrySet.iterator(); while(iterator.hasNext()){ Object o = iterator.next(); Map.Entry entry = (Map.Entry) o; System.out.println(entry.getKey() + "---->" + entry.getValue()); } } } //******************************************************************** public class User implements Comparable{ private String name; private int age; public User() { } public User(String name, int age) { this.name = name; this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public String toString() { return "User{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override public boolean equals(Object o) { System.out.println("User的equals方法"); if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; User user = (User) o; if (age != user.age) return false; return name != null ? name.equals(user.name) : user.name == null; } @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result; } //按照姓名从大到小排序,年龄从小到大排列 @Override public int compareTo(Object o) { if(o instanceof User){ User user = (User)o; // return -this.name.compareTo(user.name); int compare = -this.name.compareTo(user.name); if (compare != 0){ return compare; }else { return Integer.compare(this.age,user.age); } }else { throw new RuntimeException("输入的类型不匹配"); } } }
六、Map实现类之四：Hashtable
Hashtable 是个古老的 Map 实现类， JDK1.0 就提供了。不同于 HashMap ，
Hashtable 是线程安全的。
Hashtable 实现原理和 HashMap 相同，功能相同。底层都使用哈希表结构，查询
速度快，很多情况下可以互用。
与 HashMap 不同， Hashtable 不允许使用 null 作为 key 和 value
与 HashMap 一样， Hashtable 也不能保证其中 Key-Value 对的顺序
Hashtable 判断两个 key 相等、两个 value 相等的标准，与 HashMap 一致。
七、Map实现类之五：Properties
Properties 类是 Hashtable 的子类，该对象用于处理属性文件
由于属性文件里的 key 、 value 都是字符串类型，所以 Properties 里的 key
和 value 都是字符串类型
存取数据时，建议使用 setProperty(String key,String value) 方法和
getProperty(String key) 方法
Properties pros = new Properties();
pros .load( new FileInputStream( "jdbc.properties" ));
String user = pros .getProperty( "user" )；
System. out .println( user )
八、Map接口中定义的方法：
添加、删除、修改操作：
Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
void putAll(Map m):将m中的所有key-value对存放到当前map中
Object remove(Object key)：移除指定key的key-value对，并返回value
void clear()：清空当前map中的所有数据
元素查询的操作：
Object get(Object key)：获取指定key对应的value
boolean containsKey(Object key)：是否包含指定的key
boolean containsValue(Object value)：是否包含指定的value
int size()：返回map中key-value对的个数
boolean isEmpty()：判断当前map是否为空
boolean equals(Object obj)：判断当前map和参数对象obj是否相等
元视图操作的方法：
Set keySet()：返回所有key构成的Set集合
Collection values()：返回所有value构成的Collection集合
Set entrySet()：返回所有key-value对构成的Set集合
总结：常用方法：
添加：put()
删除：remove()
修改：put()
查询：get()
长度：size()
遍历：keySet()/values()/ entrySet()
public class MapTest { /* * 元视图操作的方法： * Set keySet()：返回所有key构成的Set集合 * Collection values()：返回所有value构成的Collection集合 * Set entrySet()：返回所有key-value对构成的Set集合 */ @Test public void test5(){ HashMap map = new HashMap(); map.put("AA",123); map.put(45,1234); map.put("BB",56); //遍历所有的key集：keySet() Set set = map.keySet(); Iterator iterator = set.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } System.out.println(); //遍历所有的value集：values() Collection values = map.values(); for(Object obj : values){ System.out.println(obj); } System.out.println(); //遍历所有的key-value //entrySet(): Set entrySet = map.entrySet(); Iterator iterator1 = entrySet.iterator(); while (iterator1.hasNext()){ //entrySet集合中的元素都是entry System.out.println(iterator1.next()); } } /* * 元素查询的操作： * Object get(Object key)：获取指定key对应的value * boolean containsKey(Object key)：是否包含指定的key * boolean containsValue(Object value)：是否包含指定的value * int size()：返回map中key-value对的个数 * boolean isEmpty()：判断当前map是否为空 * boolean equals(Object obj)：判断当前map和参数对象obj是否相等 */ @Test public void test4(){ HashMap map = new HashMap(); map.put("AA",123); map.put(45,123); map.put("BB",123); // Object get(Object key) System.out.println(map.get(45)); //containsKey(Object key) boolean isExist = map.containsKey("BB"); System.out.println(isExist); isExist = map.containsValue(123); System.out.println(isExist); map.clear(); System.out.println(map.isEmpty()); } /* * 添加、删除、修改操作： * Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中 * void putAll(Map m):将m中的所有key-value对存放到当前map中 * Object remove(Object key)：移除指定key的key-value对，并返回value * void clear()：清空当前map中的所有数据 */ @Test public void test3(){ HashMap map = new HashMap(); //添加 map.put("AA",123); map.put(45,123); map.put("BB",123); //修改 map.put("AA",87); System.out.println(map); HashMap map1 = new HashMap(); map1.put("CC",123); map1.put("DD",123); map.putAll(map1); System.out.println(map); //remove(Object key) Object value = map.remove("CCC"); System.out.println(value); System.out.println(map); //clear() map.clear();//与map = null不同 System.out.println(map.size()); System.out.println(map); } }
