10.14-Set集合、散列表

Set集合

无序集，不重复集

所谓的不重复指的是Set集合中不会出现两个equals()比较为true的元素

Set集合的实现类

• HashSet 使用散列算法实现

• TreeSet 使用二叉树来实现(不常用)

例子-无序与不重复特点

package day10_14;

import java.util.HashSet;
import java.util.Set;

public class HashSetDemo01 {
	/**
	 * Set集合:无序、不重复
	 */
	public static void main(String[] args) {
		Set<String> set = new HashSet<>();
		set.add("one");
		set.add("two");
		set.add("three");
		set.add("four");
		System.out.println(set.size());//[four, one, two, three]
		/*
		 * 元素的存放顺序与元素在集合内部的保存位置不同
		 */
		System.out.println(set);
		set.add("one");//重复添加
		//Set集合不能存入重复的元素
		System.out.println(set);//[four, one, two, three]
	}
}

例子-Set集合遍历

package day10_14;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class HashSetDemo02 {
	public static void main(String[] args) {
		Set<String> set = new HashSet<>();
		set.add("one");
		set.add("two");
		set.add("three");
		set.add("four");
		//迭代器遍历
		Iterator<String> it= set.iterator();
		while(it.hasNext()) {
			System.out.println(it.next());
		}
		//新循环遍历
		for(String s:set) {
			System.out.println(s);
		}
	}
}

对于HashSet而言，它存取元素时依赖于元素的HashCode()方法

HashCode()方法是Object类中的方法，所有的类都具备该方法，通常我们重写一个类的equals()方法时要求一并重写hashCode方法

HashCode()重写注意事项

1. hashCode()方法在被多次调用时应当返回一个稳定值，除非参与的equals()方法比较的属性发生了改变

2. 当两个对象equals()方法比较为true时，两个对象的hashCode()方法的返回值就应当相同

3. 当两个对象equals()方法比较为false时，不要求hashCode()方法的返回值不同

例子-HashSet对HashCode()的依赖

首先，创建Element.class类

package day10_14;
//测试元素的equals()与hashCode()的重写规则
public class Element {//元素类
	private int x;
	public Element(int x) {
		this.x = x;
	}
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	//重写hashCode与equals
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + x;
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Element other = (Element) obj;
		if (x != other.x)
			return false;
		return true;
	}
	
}

再创建HashSetDemo03.class测试类

package day10_14;

import java.util.HashSet;
import java.util.Set;

public class HashSetDemo03 {
	public static void main(String[] args) {
		Set<Element> set = new HashSet<>();
		Element e1 = new Element(1);
		Element e2 = new Element(1);
		System.out.println(e1==e2);//false
		System.out.println(e1.equals(e2));//未重写时，值为false；重写后，值为true
        //未重写时，值为false；重写后，值为true
		System.out.println(e1.hashCode()==e2.hashCode());
        set.add(e1);
		set.add(e2);
		System.out.println(set.size());
        //未重写时，值为2；重写后，值为1；由此可观察出HashSet的重复判断对HashCode()的依赖
	}
}

package day10_14;

import java.util.HashSet;
import java.util.Set;

public class HashSetDemo04 {
	/*
	 * 当一个元素存入HashSet集合之后，尽量不要再使用该元素的HashCode()方法
	 * 如果再使用hashCode()，方法返回值会发生变化，从而降低散列表性能
	 */
	public static void main(String[] args) {
		Set<Element> set = new HashSet<>();
		Element e = new Element(1);
		set.add(e);
		System.out.println(set.size());//1
		e.setX(2);
		set.add(e);
		//hashCode值改变，视为新元素添加
		System.out.println(set.size());//2
		e.setX(3);
		set.add(e);
		System.out.println(set.size());//3
	}
}

散列表

Map

是一个多行两列的表格，每一行储存一项

一项中包含两个部分:key-value（键值对）

其常见的实现类:HashMap(使用散列算法实现的Map)

散列表常见概念

1. 容量:散列表中散列数组的大小(不能无限大)

2. 散列运算:根据key计算散列值的算法(散列算法)

3. 散列桶:散列值相同的元素的"线性集合"

4. 加载因子:是散列数组的加载率，一般小于75%性能就比较理想(元素数量/散列数组的大小)

5. 散列查找:根据key计算散列值，根据散列值查找对应的value

6. 散列表中的key绝对不同，但value可以相同

HashMap的性能调优

加载因子的比值如果超过0.75时，散列数组将扩容；存在原数组中的数据，需要重新进行散列运算之后存入新的数组当中，并不是简单的将原数组中的数据复制到新数组中，这个过程称之为rehash(重新散列)；而这么扩容数组，rehash则会带来一定的性能开销

HashMap

以键值对的形式来存储对象，关键字Key是唯一不重复的。

1. Key可以是任意对象，value也可以是任意对象

2. Key-value需要成对放置在集合中

3. 重复key只计算一个，重复添加时后添加的value将覆盖旧value值

4. 根据key的散列值计算散列表，元素按照散列值进行排序(散列值是没有顺序的)

5. HashMap的默认容量是16，默认的加载因子是0.75

6. HashMap可以根据key检索查找value值

7. HashMap可以在构造器中指定参数:初始容量与加载因子

散列表中常用方法

V put(K k,V v)

将一对键值对存入到散列表中。

因为Map要求key不允许重复，所以当使用相同的key存入不同的元素，其操作为替换value

put返回值是被替换的value

v get(Object k)

根据给定的key获取对应的value，若是给定的key不存在，则返回null

例子

package day10_14;

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo01 {
	/**
	 * 尽管Map也是用于存取数据，
	 * 但Map不属于集合(Collection)，他们是平行关系
	 */
	public static void main(String[] args) {
		Map<String, Integer> map = new HashMap<>();
//		int num = map.put("one", 1);
//		System.out.println(num);
		//在第一次添加键值对时，put()方法会返回null,此时触发拆装箱操作会造成空指针异常
		map.put("one", 1);
		map.put("two", 2);
		map.put("three", 3);
		map.put("four", 4);
		System.out.println(map.size());//打印map的元素数量
		System.out.println(map);
		//替换
		int i = map.put("one", 100);
		System.out.println(i);
		System.out.println(map);
		//根据key获取value
		Integer v = map.get("one");
		System.out.println(v);
		//当指定的key不存在时，get()方法会返回null；此时触发拆装箱操作会造成空指针异常
		v = map.get("five");
		System.out.println(v);
		/*
		 * 查看当前Map中是否包含给定的key或者value
		 * boolean containsKey(Object k)
		 * boolean containsValue(Object v)
		 */
		System.out.println(map.containsKey("two"));//true
		System.out.println(map.containsValue(10));//false
	}
}

遍历Map的三种方式

1. 遍历所有的key

2. 遍历所有的value

3. 遍历所有的键值对

例子

package day10_14;

import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import javax.sound.midi.ControllerEventListener;

public class HashMapDemo03 {
	public static void main(String[] args) {
		Map<Integer, String> map = new HashMap<Integer, String>();
		map.put(1, "one");
		map.put(2, "two");
		map.put(3, "three");
		map.put(4, "four");
		/**
		 * 遍历所有的key
		 * Set KeySet()
		 */
		Set<Integer> KeySet = map.keySet();
		for(int key:KeySet) {
			System.out.println(key);
		}
		/*
		 * 遍历所有的value
		 * Collection values()
		 */
		Collection <String> values = map.values();
		for(String value:values) {
			System.out.println(value);
		}
		/*
		 * 遍历所有键值对
		 * Set entrySet()
		 * 每一个键值对使用Entry类的实例来描述
		 * Entry：要求定义两个泛型，来说明其描述的键值对中key与value的类型
		 * 通常我们就使用map的泛型
		 */
		Set<Entry<Integer,String>> entrySet = map.entrySet();
		for(Entry<Integer,String> entry:entrySet) {
//			System.out.println(entry);
			/*
			 * getKey()与getValue()方法分别用于一组键值对的key与value
			 */
			int key = entry.getKey();
			String value = entry.getValue();
			System.out.println(key+","+value);
		}
		
		
	}
}

例子-列表

package day10_14;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class HashMapDemo04 {
	/**
	 * HashMap的实际应用场景
	 */
	public static void main(String[] args) {
		Map<String, List<Person>> map = new HashMap<>();
		//家人
		List <Person> list1 = new ArrayList<Person>();
		list1.add(new Person("爷爷"));
		list1.add(new Person("奶奶"));
		list1.add(new Person("爸爸"));
		list1.add(new Person("妈妈"));
		//朋友
		List <Person> list2 = new ArrayList<>();
		list2.add(new Person("小明"));
		list2.add(new Person("张三"));
		list2.add(new Person("李四"));
		list2.add(new Person("王五"));
		map.put("家人", list1);
		map.put("朋友", list2);
		System.out.println(map);
	}
}
	class Person{
		private String name;
		public Person(String name) {
			this.name=name;
		}
		@Override
		public String toString() {
			return name;
		}
		
	}

HashTable(JDK1.2)

相对于HashMap来说，HashTable速度更更慢，但其更安全。

总结

集合框架(Collection和Map)

集合框架包括集合及其映射的子类

1. List集合:元素有先后次序，玄素有index位置，元素可以重复，继承于Collection接口，实现类有ArrayList/LinkedList/Vector

2. Set集合:元素无序，不能重复添加，是真正意义上的数学集合，继承自Collection接口，实现类有HashSet(是一个只有key的HashMap)/TreeSet

3. Collection:没有说明元素是否重复和有序，很少使用

4. Collections:集合的工具类

5. Map:描述了成对(key-value)放置的集合；key不可重复，value可以重复；实现类有HashMap/HashTable/TreeMap