2018-06-04 第二十九天
一、Set
Set：Collection 的子接口。
Set 规范的要求：要求 元素无序，不重复。
Set：1：HashSet；2：TreeSet。
二、HashSet
特点：元素无序的，唯一的。
底层使用的数据结构：哈希表、散列表。
例：
import java.util.HashSet;
import java.util.Iterator;
public class TestHashSet {
public static void main(String[] args) {
HashSet set = new HashSet<>();
//HashSet 的基本使用。
//添加
set.add(new Person("小张", 23, Gender.MALE));
set.add(new Person("小饼", 20, Gender.MALE));
set.add(new Person("静静",18,Gender.FEMAL));
set.add(new Person("静静",18,Gender.FEMAL));
//不能通过容器对象直接修改容器中的元素的内容
//删除
set.remove(new Person("小张", 23, Gender.MALE));
//获得--没有提供方法。
set.contains(new Person("静静",18,Gender.FEMAL));
//set.clear();
//set.size();
//set.isEmpty();
//遍历 迭代器
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Person person = iterator.next();
System.out.println(person);
}
//foreach 底层使用迭代器
for (Person person : set) {
System.out.println(person);
}
System.out.println(set);
}
}
class Person{
private String name;
private int age;
private Gender gender;
public Person() {
}
Person(String name, int age, Gender gender) {
super();
this.name = name;
this.age = age;
this.gender = gender;
}
public String toString() {
return "\nPerson [name=" + name + ", age=" + age + ", gender=" + gender + "]";
}
@Override
public int hashCode() {
System.out.println("Person.hashCode()");
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((gender == null) ? 0 : gender.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
System.out.println("Person.equals()");
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
if (age != other.age)
return false;
if (gender != other.gender)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
// public boolean equals(Object o){
// if(o == null)return false;
// if(this == o)return true;
// if(!(o instanceof Person))return false;
//
// Person p = (Person)o;
// if(!this.name.equals(p.name))
// return false;
// if(!this.gender.equals(p.gender))
// return false;
// if(this.age != p.age)
// return false;
// return true;
// }
}
enum Gender{
MALE,FEMAL
}
三、HashCode
Object 类的 hashCode() :
实际上，由Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。这一般是通过将该对象的内部地址转换成一个整数来实现的。
不同的对象的哈希码是不同的。
hashCode 的常规协定是：
在Java 应用程序执行期间，在对同一对象多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是将对象进行 equals 比较时所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。
如果根据equals(Object) 方法，两个对象是相等的，那么对这两个对象中的每个对象调用 hashCode 方法都必须生成相同的整数结果。
如果根据equals(java.lang.Object) 方法，两个对象不相等，那么对这两个对象中的任一对象上调用 hashCode 方法不 要求一定生成不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同整数结果可以提高哈希表的性能。
如果希望HahSet能够正常的工作，那么我们希望内容相同的对象的哈希码是一致的。通过调用hashCode 方法，得到的int 值是一样的。
需要在HashSet 容器中添加的元素的类型中，需要重写 hashCode 方法。用以保证相同的对象的哈希码是一致的。
如果希望HashSet 可以保证元素的唯一性和无序性，那么必须在元素对应的类型中，重写 equals 方法 和 hashCode 方法。
hashCode 方法 保证了：元素的无序（通过哈希码的值来确定元素的位置），保证了相同的对象可以具有相同的哈希码的值，保证了可以进行 equals 比较的前提。
equals 方法保证了避免相同的对象 多次添加。
总结：
HashSet 元素唯一性： hashCode() + equals
HashSet 元素无序性：hashCode()
进一步理解hashCode():
1:如果两个对象的hashCode 相同，那么equals 方法比较的结果不一定是相等。
2：如果两个对象equals 方法比较的结果是相等的，那么两个对象的hashCode 方法得到的值必须要一致。
以上两点是HashSet 可以正常工作的基础，也是hashCode 重写的依据。
哈希码又称为散列码：
重写hashCode 的依据：
1：如果两个对象equals 方法比较的结果是相等的，那么两个对象的hashCode 方法得到的值必须要一致。
2：通过equals 比较是不相等的，那么对象的hashCode 的值也要尽量的不同，以保证提高哈希表的效率。
3：希望通过hashCode 得到的值是一个均匀的散列在 int 的取值范围内的一个值。来保证哈希表中的一维数组的使用率，以及降低链表的长度。
不同的数据类型重写hashCode 的策略：
1：Integer 对象的哈希码的值就是 被封装的 int 的值。
2：String 使用一个质数 31 作为基数，然后和所有的字符值关联。
LinkedHashSet：是 HashSet 的子类。
在HashSet 的基础上，添加了一个链表。用来维护了元素添加的一个顺序。
保证了添加元素的顺序和遍历元素的顺序是一致的。但是效率有所降低。并没有提供根据索引访问元素的方法。
四、TreeSet
TreeSet：底层使用的数据结构为 树 结构 （二叉树）。
特点：唯一，有序（升序）。元素不能为null.
使用规则：
创建TreeSet 对象的时候，要么指定容器的外部比较器 java.util.Comparator 的实现的子类，要么将元素的类型实现内部比较接口 java.lang.Comparable.
在添加元素的过程中，所有的元素的大于小于，等于这些关系都是通过比较器的返回值来决定的。如果返回0 ，则认为两个元素是相等的，不再添加。
TreeSet 的执行的效率：根据内容查找的效率介于HashSet 和 ArrayList 中间。
例：
import java.util.Comparator;
import java.util.TreeSet;
import com.bjsxt.util.MyUtil;
public class TestTreeSet {
public static void main(String[] args) {
test3();
//遍历方式 迭代器 + foreach
}
static void test1(){
TreeSet set = new TreeSet<>();
set.add("abc");
set.add("efg");
set.add("cde");
set.add("rhw");
set.add("cjk");
set.add("bihaome");
System.out.println(set);
}
static void test2(){
TreeSet set = new TreeSet<>();
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
System.out.println(set);
}
static void test3(){
TreeSet set = new TreeSet<>(new Comparator() {
@Override
public int compare(Person o1, Person o2) {
return o1.getAge()-o2.getAge();
}
});
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
set.add(new Person("小刚",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL : Gender.MALE));
System.out.println(set);
}
}
class Person/* implements Comparable*/{
private String name;
private int age;
private Gender gender;
public Person() {
}
Person(String name, int age, Gender gender) {
super();
this.name = name;
this.age = age;
this.gender = gender;
}
public String toString() {
return "\nPerson [name=" + name + ", age=" + age + ", gender=" + gender + "]";
}
@Override
public int hashCode() {
System.out.println("Person.hashCode()");
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((gender == null) ? 0 : gender.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
// @Override
// public boolean equals(Object obj) {
// System.out.println("Person.equals()");
// if (this == obj)
// return true;
// if (obj == null)
// return false;
// if (getClass() != obj.getClass())
// return false;
// Person other = (Person) obj;
// if (age != other.age)
// return false;
// if (gender != other.gender)
// return false;
// if (name == null) {
// if (other.name != null)
// return false;
// } else if (!name.equals(other.name))
// return false;
// return true;
// }
// @Override
// public int compareTo(Person o) {
// return this.age - o.age;
// }
public int getAge(){
return age;
}
// public boolean equals(Object o){
// if(o == null)return false;
// if(this == o)return true;
// if(!(o instanceof Person))return false;
//
// Person p = (Person)o;
// if(!this.name.equals(p.name))
// return false;
// if(!this.gender.equals(p.gender))
// return false;
// if(this.age != p.age)
// return false;
// return true;
// }
}
五、Map
Map：映射：映射中的所有的元素都被封装成了一个Node（键+值 key+value）一个Node 包含了一对数据。
key：往往是一种数据类型相对简单的数据。
value：往往是更详细的数据的信息。
key：学号
value：学生的信息
key：身份证号码
value：人的信息。
Map：
--HashMap
--TreeMap
六、HashMap
HashMap:底层使用哈希表实现。
HashMap的工作原理：
1：将一对数据 key + value 封装成一个Node 对象。
2：将 Node 对象 放到哈希表中。通过 key 的hashCode() 得到一个哈希码，来决定放到 哈希表中的哪个位置。
通过Node 中的key 数据 来确定 整个Node 在哈希表中的位置。
结论：HashMap 中Node 的key 的特点，就是 HashSet 中的元素的特点。 HashMap 中的key 要求无序的，唯一的。
HashMap 特点：key 是无序的，唯一的，Node 是无序的，唯一的，Value 的无序的（和key 绑在一起的），不一定了。
HashMap 中的key 必须重写 equals 和 hashCode。来保证key 的唯一性 和 无序性。
HashSet 底层使用 HashMap 实现。
只使用了HashMap 的key 部分。HashSet 元素 作为 HashMap 的 key。所有的元素 都和 另外一个final static Object PRESENT 对象，作为value 被封装成了一个Node。
放到哈希表中。所以HashMap key 的特点 和 HashSet 元素的特点一致。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
原码解读：
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认的填充因子。当哈希表中的一维数组的被占用的元素的个数占数组的长度的比例达到DEFAULT_LOAD_FACTOR这个值的，时候，进行扩容。
决定了哈希表扩容的时机。避免链表过长。
//将key 和 value 封装成的Node 对象的类。内部类。Node 包含了指向下一个节点的next。
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
}
//哈希表的线性表 一维数组
transient Node[] table;
例1：
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;
public class TestHashMap2 {
public static void main(String[] args) {
HashMap map = new HashMap<>();
// 添加元素,修改
map.put("cn", "China");
map.put("us", "America");
map.put("uk", "United Kindom");
map.put("uk", "England");
map.put("jp", null);
map.put("fr", "France");
map.put(null, null);
// 删除 通过key 的哈希码找到哈希表中的位置，然后一次遍历 当前 索引的链表中的所有的Node节点中的所有的key，
// 如果key 和 某一个Node 中的key 通过euqals 比较是相等的，就移除该Node对象。
map.remove("jp");
// 获取 只能通过key 获得 对应的Node ，获取Node 中的value 值。
System.out.println(map.get("cn"));
// 其他的方法
// map.containsKey(key)
// map.clear();
// map.containsValue(value)
// map.size()
System.out.println(map.replace(null, "123"));
// 遍历 得到map 中所有的key 。
Set keySet = map.keySet();
Iterator iterator = keySet.iterator();
while (iterator.hasNext()) {
// 得到一个key
String key = iterator.next();
// 得到对应的value
String value = map.get(key);
System.out.println(key + "-->" + value);
}
// 得到所有的value ，不能得到对应的key
Collection values = map.values();
Iterator iterator2 = values.iterator();
while (iterator2.hasNext()) {
String value = iterator2.next();
System.out.println("value == " + value);
}
// 得到map 的所有的键值对。每一个键值对被封装成了一个entry
// Entry 是Map 接口的一个内部接口。一个Entry 代表了一个key 和一个value的组合。
Set> entrySet = map.entrySet();
Iterator> iterator3 = entrySet.iterator();
while (iterator3.hasNext()) {
Entry entry = iterator3.next();
String key = entry.getKey();
String value = entry.getValue();
System.out.println(key + "-->" + value);
}
System.out.println(map);
}
}
例2：
//效率测试
import java.util.HashMap;
public class TestHashMap1 {
public static void main(String[] args) {
long time = System.currentTimeMillis();
HashMap map =new HashMap<>();
final int COUNT = 200_0000;
for(int i=0;i
map.put(Integer.toString(i), Integer.toString(i));
}
long cost = System.currentTimeMillis()-time;
System.out.println("cost = "+cost);
//一秒等于1000000000纳秒（毫微秒）
time = System.nanoTime();
System.out.println("--->"+map.get("99999"));
cost = System.nanoTime()-time;
System.out.println("cost = "+cost);
// cost = 2793微秒
// --->99999
// cost = 90034毫微秒
}
}
LinkedHashMap：是在HashMap 的基础上增加了一个链表，用于维护Node 添加的顺序。
用以保证元素Node 添加的顺序和 遍历的顺序一致。但是效率有所降低。
TreeMap：底层使用二叉树来实现。
元素特点：
将key 和 value 封装成了一个Node。添加到TreeMap 中。
key 的特点 是有序（升序）的，唯一的。
和TreeSet 元素特点一致。 TreeSet 底层使用TreeMap 实现。TreeSet 只使用了TreeMap 的key 部分。
所以添加到TreeMap 中的Node 中的key 必须要么实现内部比较器java.lang.Comparable 要么指明TreeMap的外部比较器。
TreeMap 的key 不能为 null.
TreeMap 根据内容查找的效率在ArrayList 和 HashMap(最高) 之间间。
import java.util.TreeMap;
public class TestTreeMap {
public static void main(String[] args) {
TreeMap map = new TreeMap<>();
//添加元素,修改
map.put("cn", "China");
map.put("us", "America");
map.put("uk", "United Kindom");
map.put("uk", "England");
map.put("jp", null);
map.put("fr", "France");
System.out.println(map);
}
}
