于是接着去看网上的dalao的博客,发现了这一篇私自转载dalao博文侵删
HashSet实现Set接口,由哈希表(实际上是一个HashMap实例)支持。它不保证set 的迭代顺序;特别是它不保证该顺序恒久不变,此类允许使用null元素。
在HashSet中,元素都存到HashMap键值对的Key上面,而Value时有一个统一的值private static final Object PRESENT = new Object();
,(定义一个虚拟的Object对象作为HashMap的value,将此对象定义为static final。)
当有新值加入时,底层的HashMap会判断Key值是否存在(HashMap细节请移步深入理解HashMap),如果不存在,则插入新值,同时这个插入的细节会依照HashMap插入细节;如果存在就不插入
同HashMap删除原理
- public class HashSet<E>
- extends AbstractSet<E>
- implements Set<E>, Cloneable, java.io.Serializable
- {
- static final long serialVersionUID = -5024744406713321676L;
- // 底层使用HashMap来保存HashSet中所有元素。
- private transient HashMap<E,Object> map;
- // 定义一个虚拟的Object对象作为HashMap的value,将此对象定义为static final。
- private static final Object PRESENT = new Object();
- /**
- * 默认的无参构造器,构造一个空的HashSet。
- *
- * 实际底层会初始化一个空的HashMap,并使用默认初始容量为16和加载因子0.75。
- */
- public HashSet() {
- map = new HashMap<E,Object>();
- }
- /**
- * 构造一个包含指定collection中的元素的新set。
- *
- * 实际底层使用默认的加载因子0.75和足以包含指定
- * collection中所有元素的初始容量来创建一个HashMap。
- * @param c 其中的元素将存放在此set中的collection。
- */
- public HashSet(Collection<? extends E> c) {
- map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
- addAll(c);
- }
- /**
- * 以指定的initialCapacity和loadFactor构造一个空的HashSet。
- *
- * 实际底层以相应的参数构造一个空的HashMap。
- * @param initialCapacity 初始容量。
- * @param loadFactor 加载因子。
- */
- public HashSet(int initialCapacity, float loadFactor) {
- map = new HashMap<E,Object>(initialCapacity, loadFactor);
- }
- /**
- * 以指定的initialCapacity构造一个空的HashSet。
- *
- * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
- * @param initialCapacity 初始容量。
- */
- public HashSet(int initialCapacity) {
- map = new HashMap<E,Object>(initialCapacity);
- }
- /**
- * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
- * 此构造函数为包访问权限,不对外公开,实际只是是对LinkedHashSet的支持。
- *
- * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
- * @param initialCapacity 初始容量。
- * @param loadFactor 加载因子。
- * @param dummy 标记。
- */
- HashSet(int initialCapacity, float loadFactor, boolean dummy) {
- map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
- }
- /**
- * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。
- *
- * 底层实际调用底层HashMap的keySet来返回所有的key。
- * 可见HashSet中的元素,只是存放在了底层HashMap的key上,
- * value使用一个static final的Object对象标识。
- * @return 对此set中元素进行迭代的Iterator。
- */
- public Iterator<E> iterator() {
- return map.keySet().iterator();
- }
- /**
- * 返回此set中的元素的数量(set的容量)。
- *
- * 底层实际调用HashMap的size()方法返回Entry的数量,就得到该Set中元素的个数。
- * @return 此set中的元素的数量(set的容量)。
- */
- public int size() {
- return map.size();
- }
- /**
- * 如果此set不包含任何元素,则返回true。
- *
- * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。
- * @return 如果此set不包含任何元素,则返回true。
- */
- public boolean isEmpty() {
- return map.isEmpty();
- }
- /**
- * 如果此set包含指定元素,则返回true。
- * 更确切地讲,当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))
- * 的e元素时,返回true。
- *
- * 底层实际调用HashMap的containsKey判断是否包含指定key。
- * @param o 在此set中的存在已得到测试的元素。
- * @return 如果此set包含指定元素,则返回true。
- */
- public boolean contains(Object o) {
- return map.containsKey(o);
- }
- /**
- * 如果此set中尚未包含指定元素,则添加指定元素。
- * 更确切地讲,如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2))
- * 的元素e2,则向此set 添加指定的元素e。
- * 如果此set已包含该元素,则该调用不更改set并返回false。
- *
- * 底层实际将将该元素作为key放入HashMap。
- * 由于HashMap的put()方法添加key-value对时,当新放入HashMap的Entry中key
- * 与集合中原有Entry的key相同(hashCode()返回值相等,通过equals比较也返回true),
- * 新添加的Entry的value会将覆盖原来Entry的value,但key不会有任何改变,
- * 因此如果向HashSet中添加一个已经存在的元素时,新添加的集合元素将不会被放入HashMap中,
- * 原来的元素也不会有任何改变,这也就满足了Set中元素不重复的特性。
- * @param e 将添加到此set中的元素。
- * @return 如果此set尚未包含指定元素,则返回true。
- */
- public boolean add(E e) {
- return map.put(e, PRESENT)==null;
- }
- /**
- * 如果指定元素存在于此set中,则将其移除。
- * 更确切地讲,如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e,
- * 则将其移除。如果此set已包含该元素,则返回true
- * (或者:如果此set因调用而发生更改,则返回true)。(一旦调用返回,则此set不再包含该元素)。
- *
- * 底层实际调用HashMap的remove方法删除指定Entry。
- * @param o 如果存在于此set中则需要将其移除的对象。
- * @return 如果set包含指定元素,则返回true。
- */
- public boolean remove(Object o) {
- return map.remove(o)==PRESENT;
- }
- /**
- * 从此set中移除所有元素。此调用返回后,该set将为空。
- *
- * 底层实际调用HashMap的clear方法清空Entry中所有元素。
- */
- public void clear() {
- map.clear();
- }
- /**
- * 返回此HashSet实例的浅表副本:并没有复制这些元素本身。
- *
- * 底层实际调用HashMap的clone()方法,获取HashMap的浅表副本,并设置到HashSet中。
- */
- public Object clone() {
- try {
- HashSet<E> newSet = (HashSet<E>) super.clone();
- newSet.map = (HashMap<E, Object>) map.clone();
- return newSet;
- } catch (CloneNotSupportedException e) {
- throw new InternalError();
- }
- }
- }
1. HashMap概述:
https://zhangshixi.iteye.com/blog/672697
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
2. HashMap的数据结构
HashMap是一个数组和链表结合的数据结构
从上图中可以看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。
可以看出,Entry就是数组中的元素,每个 Map.Entry 其实就是一个key-value对,它持有一个指向下一个元素的引用,这就构成了链表。
- /**
- * The table, resized as necessary. Length MUST Always be a power of two.
- */
- transient Entry[] table;
- static class Entry<K,V> implements Map.Entry<K,V> {
- final K key;
- V value;
- Entry<K,V> next;
- final int hash;
- ……
- }
当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。
hashMap中的key-value对时,完全没有考虑Entry中的value,仅仅只是根据key来计算并决定每个Entry的存储位置
addEntry(hash, key, value, i)方法根据计算出的hash值,将key-value对放在数组table的i索引处。addEntry 是 HashMap 提供的一个包访问权限的方法
- public V put(K key, V value) {
- // HashMap允许存放null键和null值。
- // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
- if (key == null)
- return putForNullKey(value);
- // 根据key的keyCode重新计算hash值。
- int hash = hash(key.hashCode());
- // 搜索指定hash值在对应table中的索引。
- int i = indexFor(hash, table.length);
- // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。
- for (Entry<K,V> e = table[i]; e != null; e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- // 如果i索引处的Entry为null,表明此处还没有Entry。
- modCount++;
- // 将key、value添加到i索引处。
- addEntry(hash, key, value, i);
- return null;
- }
通过传入的hash值和数组的长度来计算 map存放数组的位置,为了保证数据均匀分布在数组上,不会出现 通过key 计算的hash值重复而将 数据放到链表中。所以数组的长度要是 2^n
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
这段代码保证初始化时HashMap的容量总是2的n次方,即底层数组的长度总是为2的n次方。当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。
- int capacity = 1;
- while (capacity < initialCapacity)
- capacity <<= 1;
HashMap遍历
- Map<String, String> map = new HashMap<String, String>();
- for (Entry<String, String> entry : map.entrySet()) {
- entry.getKey();
- entry.getValue();
- }
- Map<String, String> map = new HashMap<String, String>();
- for (String key : map.keySet()) {
- map.get(key);
- }
- Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
- while (iterator.hasNext()) {
- Map.Entry<String, String> entry = iterator.next();
- entry.getKey();
- entry.getValue();
- }
HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。
归纳起来简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。
- public V get(Object key) {
- if (key == null)
- return getForNullKey();
- int hash = hash(key.hashCode());
- for (Entry<K,V> e = table[indexFor(hash, table.length)];
- e != null;
- e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
- return e.value;
- }
- return null;
- }
HashMap的实现中,通过threshold字段来判断HashMap的最大容量:
Java代码
结合负载因子的定义公式可知,threshold就是在此loadFactor和capacity对应下允许的最大元素数目,超过这个数目就重新resize,以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时, resize后的HashMap容量是容量的两倍:
Java代码
如果既需要key也需要value,直接用KeySet 遍历,
HashMap在并发执行put会引起死循环,是因为多线程会导致HashMap的Entry链表成环,一旦成环,Entry的next节点永远不为空,产生死循环
效率低下的HashTable 线程安全的Map类,其public方法均用synchronize修饰
如线程1使用put进行元素添加,线程2不但不能使用put方法进行添加元素,也不能使用get方法来获取元素,所以竞争越激烈效率越低,这必然导致多线程时性能不佳.另外,Hashtable不能使用null作为key/value
concurrentHashMap:线程安全支持并发操作
ConcurrentHashMap的工作机制,通过把整个Map分为N个Segment(类似HashTable),可以提供相同的线程安全,但是效率提升N倍,默认提升16倍
我们再来具体了解一下Segment的数据结构:
1 2 3 4 5 6 7 |
|
详细解释一下Segment里面的成员变量的意义:
Segment中的元素是以HashEntry的形式存放在链表数组中的,看一下HashEntry的结构:
1 2 3 4 5 6 |
|
可以看到HashEntry的一个特点,除了value以外,其他的几个变量都是final的,这样做是为了防止链表结构被破坏,出现ConcurrentModification的情况。
ArrayList底层原理
ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,在Java 8中是默认扩展为原来的1.5倍,如果能确定数组的大小一般指定数组长度不要频繁的进行扩容
线程不安全的,只能用在单线程环境下,多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类,也可以使用concurrent并发包下的CopyOnWriteArrayList类。
ArrayList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了RandomAccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问
ArrayList 源码基本操作是对数组的操作
- /**
- * Default initial capacity.
- */
- private static final int DEFAULT_CAPACITY = 10;
- /**
- * Shared empty array instance used for empty instances.
- */
- private static final Object[] EMPTY_ELEMENTDATA = {};
- /**
- * Shared empty array instance used for default sized empty instances. We
- * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
- * first element is added.
- */
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- /**
- * The array buffer into which the elements of the ArrayList are stored.
- * The capacity of the ArrayList is the length of this array buffer. Any
- * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
- * will be expanded to DEFAULT_CAPACITY when the first element is added.
- */
- transient Object[] elementData; // non-private to simplify nested class access
- /**
- * The size of the ArrayList (the number of elements it contains).
- *
- * @serial
- */
- private int size;
首先是一个常量DEFAULT_CAPACITY,根据注释表示默认的长度为10。然后是一个EMPTY_ELEMENTDATA的常量object数组,只是空有其表没有内容。然后是一个object数组elementData。
这个就是最重要的成员了,通过注释我们可以看到这表示这个数组用来存储我们的数据。也就是说,我们代码中的add的数据都会放在这个数组里面。那么由此我们可知,ArrayList内部是由数组实现。再看最后一个变量,int类型的size。
第一眼还以为是elementData数组的长度。仔细看注释,才发现它表示的是elementData数组里面包含的数据长度。
元素存储
- // 用指定的元素替代此列表中指定位置上的元素,并返回以前位于该位置上的元素。
- 21 public E set(int index, E element) {
- 22 RangeCheck(index);
- 23
- 24 E oldValue = (E) elementData[index];
- 25 elementData[index] = element;
- 26 return oldValue;
- 27 }
- 28 // 将指定的元素添加到此列表的尾部。
- 29 public boolean add(E e) {
- 30 ensureCapacity(size + 1);
- 31 elementData[size++] = e;
- 32 return true;
- 33 }
- 34 // 将指定的元素插入此列表中的指定位置。
- 35 // 如果当前位置有元素,则向右移动当前位于该位置的元素以及所有后续元素(将其索引加1)。
- 36 public void add(int index, E element) {
- 37 if (index > size || index < 0)
- 38 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
- 39 // 如果数组长度不足,将进行扩容。
- 40 ensureCapacity(size+1); // Increments modCount!!
- 41 // 将 elementData中从Index位置开始、长度为size-index的元素,
- 42 // 拷贝到从下标为index+1位置开始的新的elementData数组中。
- 43 // 即将当前位于该位置的元素以及所有后续元素右移一个位置。
- 44 System.arraycopy(elementData, index, elementData, index + 1, size - index);
- 45 elementData[index] = element;
- 46 size++;
- 47 }
- 48 // 按照指定collection的迭代器所返回的元素顺序,将该collection中的所有元素添加到此列表的尾部。
- 49 public boolean addAll(Collection<? extends E> c) {
- 50 Object[] a = c.toArray();
- 51 int numNew = a.length;
- 52 ensureCapacity(size + numNew); // Increments modCount
- 53 System.arraycopy(a, 0, elementData, size, numNew);
- 54 size += numNew;
- 55 return numNew != 0;
- 56 }
- 57 // 从指定的位置开始,将指定collection中的所有元素插入到此列表中。
- 58 public boolean addAll(int index, Collection<? extends E> c) {
- 59 if (index > size || index < 0)
- 60 throw new IndexOutOfBoundsException(
- 61 "Index: " + index + ", Size: " + size);
- 62
- 63 Object[] a = c.toArray();
- 64 int numNew = a.length;
- 65 ensureCapacity(size + numNew); // Increments modCount
- 66
- 67 int numMoved = size - index;
- 68 if (numMoved > 0)
- 69 System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
- 70
- 71 System.arraycopy(a, 0, elementData, index, numNew);
- 72 size += numNew;
- 73 return numNew != 0;
- }
元素读
- // 返回此列表中指定位置上的元素。
- public E get(int index) {
- RangeCheck(index);
- return (E) elementData[index];
- }
元素删除ArrayList提供了根据下标或者指定对象两种方式的删除功能。如下: romove(int index):
- // 移除此列表中指定位置上的元素。
- 2 public E remove(int index) {
- 3 RangeCheck(index);
- 4
- 5 modCount++;
- 6 E oldValue = (E) elementData[index];
- 7
- 8 int numMoved = size - index - 1;
- 9 if (numMoved > 0)
- 10 System.arraycopy(elementData, index+1, elementData, index, numMoved);
- 11 elementData[--size] = null; // Let gc do its work
- 12
- 13 return oldValue;
- 14 }
联系客服