一、Set类的作用
二、Set类延生的四种形式
三、非基础类型如何使用Set的四种形式
四、Queue的使用
五、PriorityQueue的使用
六、Map的六种形式
七、HashMap散列码的实现
八、如何制作优秀的散列码
回答：
1、Set的特点：①、存入Set的每个元素在Set中都是唯一的 ②、输出的时候不保证元素的次序
2、Set延生的四种类型：
①、HashSet：为快速查找而设计的，存入Set的元素必须实现hashCode()方法
②、TreeSet:输出的时候保证元素的优先顺序（不是按照输入时候的顺序，而是根据元素的大小）。存入Set的元素必须实现Comparable接口
③、LinkedHashSet:具有HashSet快速查找的特性。还能够按照输入Set的顺序输出数据， 存入Set的元素必须实现hashCode()方法
④、SortedSet:对TreeSet的扩展，扩展了一些方法。（获取头，尾元素的方法。截取容器中部分元素的方法等）
3、对各种类型的使用。
步骤①、制作原始类TestType，制作HashCodeType继承TestType重写hashCode()方法，制作ComparableType继承TestType和Comparable接口
public class TestType {
protected int index;
public TestType(int index){
this.index = index;
}
public int getIndex(){
return index;
}
@Override
public String toString() {
return "TestType [index=" + index + "]";
}
}
TestType
public class HashCodeType extends TestType {
public HashCodeType(int index) {
super(index);
// TODO Auto-generated constructor stub
}
@Override
public int hashCode() {
// TODO Auto-generated method stub
return index;
}
@Override
public boolean equals(Object obj) {
// TODO Auto-generated method stub
//判断是否是相同类比较。
if (obj instanceof TestType && ((TestType) obj).getIndex() == index){
return true;
}
else {
return false;
}
}
}
HashCodeType
public class ComparableType extends TestType implements Comparable<ComparableType>{
public ComparableType(int index) {
super(index);
// TODO Auto-generated constructor stub
}
@Override
public int compareTo(ComparableType o) {
// TODO Auto-generated method stub
if (index > o.getIndex()){
return -1;
}
else if (index == o.getIndex()){
return 0;
}
else {
return 1;
}
}
}
ComparableType
②、进行测试
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
fill(new HashSet<TestType>(), TestType.class);
fill(new LinkedHashSet<HashCodeType>(), HashCodeType.class);
fill(new TreeSet<>(), ComparableType.class);
}
public static <E> void fill(Set<E> set,Class<E> type ){
for(int i=0; i<10; ++i){
//通过反射创建类
try {
Constructor<E> constructor = type.getConstructor(int.class);
set.add(constructor.newInstance(i));
} catch (NoSuchMethodException | SecurityException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (InstantiationException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IllegalAccessException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IllegalArgumentException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (InvocationTargetException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
System.out.println(set.toString());
}
}
/**
*输出：
*[TestType [index=4], TestType [index=7], TestType [index=8], TestType [index=0], TestType [index=6], TestType [index=1], TestType [index=2], TestType [index=3], TestType [index=5], TestType [index=9]]
[TestType [index=0], TestType [index=1], TestType [index=2], TestType [index=3], TestType [index=4], TestType [index=5], TestType [index=6], TestType [index=7], TestType [index=8], TestType [index=9]]
[TestType [index=9], TestType [index=8], TestType [index=7], TestType [index=6], TestType [index=5], TestType [index=4], TestType [index=3], TestType [index=2], TestType [index=1], TestType [index=0]]
*/
Main
四、Queue的使用
①、顾名思义按照先进先出的顺序执行。 ②、除了ProrityQueue不是按照该顺序执行
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
//不介绍队列的种类，但要知道LinkedList是一个队列
Queue<Integer> data = new LinkedList<>();
for(int i=0; i<10; ++i){
//添加数据
data.offer(i);
}
//返回顶部数据
while(data.peek() != null){
//移除顶部数据，并返回该条数据
System.out.println(data.remove()+" ");
}
}
}
Main
PriorityQueue的使用详解
①、需要继承Comparable接口，确定优先级 ②、可分为多层优先级（等会示例可以看到）
public class ProrityItem implements Comparable<ProrityItem>{
public char firstPrority;
public int secondPrority;
private String name;
public ProrityItem(char firstPrority, int secondPrority, String name) {
this.firstPrority = firstPrority;
this.secondPrority = secondPrority;
this.name = name;
}
@Override
public String toString() {
return "ProrityItem [firstPrority=" + firstPrority + ", secondPrority="
+ secondPrority + ", name=" + name + "]";
}
@Override
public int compareTo(ProrityItem o) {
// TODO Auto-generated method stub
//第一级优先级
if (firstPrority > o.firstPrority){
return 1;
}
else if (firstPrority == o.firstPrority){
//第二层优先级
if (secondPrority > o.secondPrority){
return 1;
}
else if (secondPrority == o.secondPrority) {
return 0;
}
else {
return -1;
}
}
else {
return -1;
}
}
}
PriorityItem
public class Main {
public static void main(String[] args){
PriorityQueue<ProrityItem> queue = new PriorityQueue<>();
queue.add(new ProrityItem('B', 1, "你好"));
queue.add(new ProrityItem('A', 6, "HaHa"));
queue.add(new ProrityItem('A', 2, "Yes"));
//不要用toString方法，数据结果不符
while(queue.peek()!= null){
System.out.println(queue.remove()+" ");
}
}
}
/*
*ProrityItem [firstPrority=A, secondPrority=2, name=Yes]
*ProrityItem [firstPrority=A, secondPrority=6, name=HaHa]
*ProrityItem [firstPrority=B, secondPrority=1, name=你好]
*
*/
Main
五、Map
Map的种类：
HashMap、TreeMap、
LinkedHashMap：首次查询输出时候按照插入的顺序， 注意：当查找的时候，查询次数高的会被排在后面，查询次数少的会被排在前面。
举例：就是我存入了1 ，2 ，3 当一开始查询 时候输出是1 ，2 ，3 。但是当我查了 1之后，我再查询全部的时候，输出的就是 2, 3, 1
WeakHashMap：弱类型，容易被垃圾回收机制回收
ConcurrentHashMap：多线程情况下使用的map
SortMap:形式同SortSet都是TreeMap的延生
Map的散列原理（继承AbstractMap实现原生的HashMap）：
①、了解散列码的原理和快速查找的原理
首先散列集是由一段数组组成的，每个数组的控件称为桶。
通过数学公式将hashCode()方法中获取到的数据转换为数组的下标，找到对应的桶。
桶中存储的是一个容器对象（Collection），因为可能会有hashCode()转换成下标相同的情况。将hash值相同的对象放入容器中。
查找：
因为容器的查找，是从头开始一个个匹配的原则。
散列码能够先快速定位到相同的位置，再进行依次匹配。这样就能够减少其他不必要的查找，从而增加了效率。
②、制作HashMap
步骤①、继承AbstratMap类，确定桶的个数，桶中装载哪种容器。
public class MyHashMap<K,V> extends AbstractMap<K, V>{
//桶的数量
private static final int BARREL_COUNT = 937;
//使用ArrayList作为容器
private ArrayList<Entry<K, V>> [] barrels;
//为返回Set做准备
private Set<java.util.Map.Entry<K, V>> mSet;
public MyHashMap(){
barrels = new ArrayList [BARREL_COUNT];
mSet = new HashSet<>();
}
}
MyHashMap
步骤②、创建HashEntry类继承Entry接口。用来存储key和value
class MyEntry implements Entry<K, V>{
private K key;
private V value;
public MyEntry(K key,V value){
this.key = key;
this.value = value;
}
@Override
public K getKey() {
// TODO Auto-generated method stub
return key;
}
@Override
public V getValue() {
// TODO Auto-generated method stub
return value;
}
@Override
public V setValue(V value) {
// TODO Auto-generated method stub
V oldValue = this.value;
this.value = value;
return oldValue;
}
}
MyEntry
步骤③、重写put方法 1、当放入数据的时候，先获key的hashCode转换为桶的下标 2、根据下标寻找桶对应 的容器，如果容器没被创建则创建，并将数据转换为Entry装入容器中（也装入Set这个容器中）。 3、如果容器被创建了，之后获取容器，并将容器中的Entry拿出来和放入数据的key进行判断，是否已经存在。如果已经存在则替换，如果不存在则将entry装入容器中（也装入Set这个容器中）。
@Override
public V put(K key, V value) {
//注意：常用获取索引的方法就是根据数组的大小取余 ①
int index = Math.abs(key.hashCode())%BARREL_COUNT;
ArrayList<Entry<K, V>> list = barrels[index];
MyEntry entry = new MyEntry(key, value);
//判断容器是否存在
if (list == null){
barrels[index] = new ArrayList<>();
barrels[index].add(entry);
mSet.add(entry);
return value;
}
else{
//查找是否key已经存在
boolean found = false;
for(Entry<K, V> myEntry: list){
if (myEntry.getKey().equals(key)){
V oldValue = myEntry.getValue();
myEntry.setValue(value);
found = true;
return oldValue;
}
}
//不存在则装入List中
if (!found){
list.add(entry);
}
return value;
}
}
MyHashMap
步骤④、重写get方法 1、获取key的hashCode转换为桶的下标 2、根据下标寻找容器，如果容器不存在返回false，如果容器存在，则拿出entry与key进行比较。如果成功则返回value，不成功返回null
public V get(Object key) {
int index =Math.abs(key.hashCode())%BARREL_COUNT;
ArrayList<Entry<K, V>> list = barrels[index];
if (list == null){
return null;
}
else {
boolean found = false;
for(Entry<K, V> myEntry: list){
if (myEntry.getKey().equals(key)){
return myEntry.getValue();
}
}
return null;
}
}
MyHashMap
步骤⑤、创建Set 将 所有的entry装入Set中
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return mSet;
}
MyHashMap
如何制作好的散列码：
判定方法：①、hashCode()应该产生分布均匀的散列码。
如何制作：①、根据对象内容生成散列码 ②、首先给int result 初始化一个非0值 例如：int result = 7; ③、对每个可修改的成员变量计算出本身的散列码 比如：人 有 姓名和性别 所以需要对姓名和性别分别制作散列码。
④、合并计算。
举例：
public class HashTest {
public String str;
public int data;
public HashTest(String str,int data){
this.str = str;
this.data = data;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof HashTest){
HashTest test = (HashTest)obj;
if (test.str == str && test.data == data){
return true;
}
else {
return false;
}
}
return false;
}
@Override
public int hashCode() {
//第一步，给result赋值
int result = 17;
//第二步给可改变的成员变量对应的值
int strHash = str.hashCode();
int dataHash = data;
//第三步：合并值
result = 10*result + strHash;
result = 10*result + dataHash;
return result;
}
}
HashTest