java（八）集合（2）

集合

1、HashMap：定义：基于哈希表的 Map 接口的实现，以key-value的形式存在，key-value总是会当做一个整体来处理，系统会根据hash算法来来计算key-value的存储位置。继承自AbstractMap。

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable 2、构造函数：1）HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。2）HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。3）HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。 初始容量：表示哈希表中桶的容量，加载因子表示哈希表其容量自动增加之前可以达到多满的一种尺度，衡量散列表空间的使用程度。负载因子越大表示散列表的装填程度越高，反之愈小，使用链表法的散列表查找一个元素的平均时间是O(1+a)，如果负载因子越大，对空间的利用更充分，后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况无需修改。

3、内部结构：Hashmap是一个链表散列支持快速存取的结构

Hashmap 的底层是数组，但是数组的每一项都是链表,（HashMap的构造函数）

public HashMap(int initialCapacity, float loadFactor) { //初始容量不能<0 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //初始容量不能 > 最大容量值，HashMap的最大容量值为2^30 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //负载因子不能 < 0 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。 int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; //设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作 threshold = (int) (capacity * loadFactor); //初始化table数组 table = new Entry[capacity]; init(); } initialCapacity代表了该数组的长度，每次新建一个HashMap时会初始化一个table数组。table数组的元素为Entry节点。

static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } ....... } Entry为HashMap的内部类，它包含了键key、值value、下一个节点next，以及hash值，正是由于Entry才构成了table数组的项为链表。 4、HashMap的存操作：

存数据源码

public V put(K key, V value) { //当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因 if (key == null) return putForNullKey(value); //计算key的hash值 int hash = hash(key.hashCode()); ------(1) //计算key hash 值在 table 数组中的位置 int i = indexFor(hash, table.length); ------(2) //从i出开始迭代 e,找到 key 保存的位置 for (Entry<K, V> e = table[i]; e != null; e = e.next) { Object k; //判断该条链上是否有hash值相同的(key相同) //若存在相同，则直接覆盖value，返回旧value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; //旧值 = 新值 e.value = value; e.recordAccess(this); return oldValue; //返回旧值 } } //修改次数增加1 modCount++; //将key、value添加至i位置处 addEntry(hash, key, value, i); return null; } 存储过程是。先判断要保存的数据key是否为null，为null调用putForNullKey方法，不为空计算key的哈希值，根据哈希值搜索数组中索引位置，如果数组中该位置有元素，比较key值知否相同，如果相同覆盖原key下的value（确保没有相同的key），如果不同保存在链头，最先保存的元素在链尾，若数组中没有该元素直接保存。http://www.cnblogs.com/chenssy/p/3521565.html 5、HashMap的取操作：

public V get(Object key) { // 若为null，调用getForNullKey方法返回相对应的value if (key == null) return getForNullKey(); // 根据该 key 的 hashCode 值计算它的 hash 码 int hash = hash(key.hashCode()); // 取出 table 数组中指定索引处的值 for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //若搜索的key与查找的key相同，则返回相对应的value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; } 通过key的hash值找到在table数组中的索引处的Entry，然后返回该key对应的value

HashSet

HashSet继承AbstractSet类，实现Set、Cloneable、Serializable接口，底层用HashMap来保存元素。

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { // 使用 HashMap 的 key 保存 HashSet 中所有元素 private transient HashMap<E,Object> map; // 定义一个虚拟的 Object 对象作为 HashMap 的 value private static final Object PRESENT = new Object(); ... // 初始化 HashSet，底层会初始化一个 HashMap public HashSet() { map = new HashMap<E,Object>(); } // 以指定的 initialCapacity、loadFactor 创建 HashSet // 其实就是以相应的参数创建 HashMap public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<E,Object>(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap<E,Object>(initialCapacity); } HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<E,Object>(initialCapacity , loadFactor); } // 调用 map 的 keySet 来返回所有的 key public Iterator<E> iterator() { return map.keySet().iterator(); } // 调用 HashMap 的 size() 方法返回 Entry 的数量，就得到该 Set 里元素的个数 public int size() { return map.size(); } // 调用 HashMap 的 isEmpty() 判断该 HashSet 是否为空， // 当 HashMap 为空时，对应的 HashSet 也为空 public boolean isEmpty() { return map.isEmpty(); } // 调用 HashMap 的 containsKey 判断是否包含指定 key //HashSet 的所有元素就是通过 HashMap 的 key 来保存的 public boolean contains(Object o) { return map.containsKey(o); } // 将指定元素放入 HashSet 中，也就是将该元素作为 key 放入 HashMap public boolean add(E e) { return map.put(e, PRESENT) == null; } // 调用 HashMap 的 remove 方法删除指定 Entry，也就删除了 HashSet 中对应的元素 public boolean remove(Object o) { return map.remove(o)==PRESENT; } // 调用 Map 的 clear 方法清空所有 Entry，也就清空了 HashSet 中所有元素 public void clear() { map.clear(); } ... } HashSet 的实现其实非常简单，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。  HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。  iterator()方法返回对此 set 中元素进行迭代的迭代器。返回元素的顺序并不是特定的。底层调用HashMap的keySet返回所有的key，这点反应了HashSet中的所有元素都是保存在HashMap的key中，value则是使用的PRESENT对象，该对象为static final。

size()返回此 set 中的元素的数量（set 的容量）。底层调用HashMap的size方法，返回HashMap容器的大小。

isEmpty()，判断HashSet()集合是否为空，为空返回 true，否则返回false。

contains()，判断某个元素是否存在于HashSet()中，存在返回true，否则返回false。更加确切的讲应该是要满足这种关系才能返回true：(o==null ? e==null : o.equals(e))。底层调用containsKey判断HashMap的key值是否为空。

add()如果此 set 无此元素则添加此元素。如果此Set没有包含满足(e==null ? e2==null : e.equals(e2)) 的e2时，则将e2添加到Set中，否则不添加且返回false。由于底层使用HashMap的put方法将key = e，value=PRESENT构建成key-value键值对，当此e存在于HashMap的key中，则value将会覆盖原有value，但是key保持不变，所以如果将一个已经存在的e元素添加中HashSet中，新添加的元素是不会保存到HashMap中，所以这就满足了HashSet中元素不会重复的特性。

remove如果指定元素存在于此 set 中，则将其移除。底层使用HashMap的remove方法删除指定的Entry。

clear从此 set 中移除所有元素。底层调用HashMap的clear方法清除所有的Entry。