于是接着去看网上的dalao的博客,发现了这一篇私自转载dalao博文侵删
HashSet概述和实现
HashSet实现Set接口,由哈希表(实际上是一个HashMap实例)支持。它不保证set 的迭代顺序;特别是它不保证该顺序恒久不变,此类允许使用null元素。
在HashSet中,元素都存到HashMap键值对的Key上面,而Value时有一个统一的值private static final Object PRESENT = new Object(); ,(定义一个虚拟的Object对象作为HashMap的value,将此对象定义为static final。)
HashSet插入
当有新值加入时,底层的HashMap会判断Key值是否存在(HashMap细节请移步深入理解HashMap),如果不存在,则插入新值,同时这个插入的细节会依照HashMap插入细节;如果存在就不插入
删除
同HashMap删除原理
源码分析
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。 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)); * 以指定的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 加载因子。 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(); * 底层实际调用HashMap的size()方法返回Entry的数量,就得到该Set中元素的个数。 * @return 此set中的元素的数量(set的容量)。 * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。 * @return 如果此set不包含任何元素,则返回true。 public boolean isEmpty() { * 更确切地讲,当且仅当此set包含一个满足(o==null ? e==null : o.equals(e)) * 底层实际调用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)) * 如果此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中元素不重复的特性。 * @return 如果此set尚未包含指定元素,则返回true。 public boolean add(E e) { return map.put(e, PRESENT)==null; * 更确切地讲,如果此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中所有元素。 * 返回此HashSet实例的浅表副本:并没有复制这些元素本身。 * 底层实际调用HashMap的clone()方法,获取HashMap的浅表副本,并设置到HashSet中。 HashSet<E> newSet = (HashSet<E>) super.clone(); newSet.map = (HashMap<E, Object>) map.clone(); } catch (CloneNotSupportedException e) { throw new InternalError();
注意
- 说白了,HashSet就是限制了功能的HashMap,所以了解HashMap的实现原理,这个HashSet自然就通
- 对于HashSet中保存的对象,主要要正确重写equals方法和hashCode方法,以保证放入Set对象的唯一性
- 虽说是Set是对于重复的元素不放入,倒不如直接说是底层的Map直接把原值替代了(这个Set的put方法的返回值真有意思)
- HashSet没有提供get()方法,愿意是同HashMap一样,Set内部是无序的,只能通过迭代的方式获得
1. HashMap概述:
https://zhangshixi./blog/672697
JDK1.8修改
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. static class Entry<K,V> implements Map.Entry<K,V> {
HashMap 存储元素
当我们往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放置在数组第一个位置。 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) { if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 如果i索引处的Entry为null,表明此处还没有Entry。 addEntry(hash, key, value, i);
通过传入的hash值和数组的长度来计算 map存放数组的位置,为了保证数据均匀分布在数组上,不会出现 通过key 计算的hash值重复而将 数据放到链表中。所以数组的长度要是 2^n
static int indexFor(int h, int length) {
这段代码保证初始化时HashMap的容量总是2的n次方,即底层数组的长度总是为2的n次方。当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。
while (capacity < initialCapacity)
归纳起来简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。
HashMap遍历
Map<String, String> map = new HashMap<String, String>(); for (Entry<String, String> entry : map.entrySet()) { Map<String, String> map = new HashMap<String, String>(); for (String key : map.keySet()) { Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<String, String> entry = iterator.next();
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) { int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
HashMap扩容
HashMap的实现中,通过threshold字段来判断HashMap的最大容量:
Java代码
- threshold = (int)(capacity * loadFactor);
结合负载因子的定义公式可知,threshold就是在此loadFactor和capacity对应下允许的最大元素数目,超过这个数目就重新resize,以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时, resize后的HashMap容量是容量的两倍:
Java代码
- if (size++ >= threshold)
- resize(2 * table.length);
如果既需要key也需要value,直接用KeySet 遍历,
ConcurrentHashMap 和 HashMap
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
我们再来具体了解一下Segment的数据结构:
1
2
3
4
5
6
7
|
static final class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile int count;
transient int modCount;
transient int threshold;
transient volatile HashEntry<K,V>[] table;
final float loadFactor;
}
|
详细解释一下Segment里面的成员变量的意义:
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).
首先是一个常量DEFAULT_CAPACITY,根据注释表示默认的长度为10。然后是一个EMPTY_ELEMENTDATA的常量object数组,只是空有其表没有内容。然后是一个object数组elementData。
这个就是最重要的成员了,通过注释我们可以看到这表示这个数组用来存储我们的数据。也就是说,我们代码中的add的数据都会放在这个数组里面。那么由此我们可知,ArrayList内部是由数组实现。再看最后一个变量,int类型的size。
第一眼还以为是elementData数组的长度。仔细看注释,才发现它表示的是elementData数组里面包含的数据长度。
元素存储
// 用指定的元素替代此列表中指定位置上的元素,并返回以前位于该位置上的元素。 21 public E set(int index, E element) { 24 E oldValue = (E) elementData[index]; 25 elementData[index] = element; 29 public boolean add(E e) { 30 ensureCapacity(size + 1); 31 elementData[size++] = e; 35 // 如果当前位置有元素,则向右移动当前位于该位置的元素以及所有后续元素(将其索引加1)。 36 public void add(int index, E element) { 37 if (index > size || index < 0) 38 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); 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; 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); 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); 63 Object[] a = c.toArray(); 64 int numNew = a.length; 65 ensureCapacity(size + numNew); // Increments modCount 67 int numMoved = size - index; 69 System.arraycopy(elementData, index, elementData, index + numNew, numMoved); 71 System.arraycopy(a, 0, elementData, index, numNew);
元素读
public E get(int index) { return (E) elementData[index];
元素删除ArrayList提供了根据下标或者指定对象两种方式的删除功能。如下: romove(int index):
2 public E remove(int index) { 6 E oldValue = (E) elementData[index]; 8 int numMoved = size - index - 1; 10 System.arraycopy(elementData, index+1, elementData, index, numMoved); 11 elementData[--size] = null; // Let gc do its work
|