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.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));

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));

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);

}

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,686评论 6赞 492
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,668评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 158,160评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,736评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,847评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,043评论 1赞 291
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,129评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,872评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,318评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,645评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,777评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,470评论 4赞 333
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,126评论 3赞 317
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,861评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,095评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,589评论 2赞 362
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,687评论 2赞 351

2018-06-04 第二十九天

推荐阅读更多精彩内容