html5移动端网站开发,wordpress 访问者,新乡网站优化,注销公司需要什么资料和流程主要内容集合框架体系ArrayListLinkedListHashSetTreeSetLinkedHashSet内部比较器和外部比较器哈希表的原理List集合List集合的主要实现类有ArrayList和LinkedList#xff0c;分别是数据结构中顺序表和链表的实现。另外还包括栈和队列的实现类#xff1a;Deque和Queue。• Li…主要内容集合框架体系ArrayListLinkedListHashSetTreeSetLinkedHashSet内部比较器和外部比较器哈希表的原理List集合List集合的主要实现类有ArrayList和LinkedList分别是数据结构中顺序表和链表的实现。另外还包括栈和队列的实现类Deque和Queue。• List • 特点有序 不唯一可重复• ArrayList • 在内存中分配连续的空间实现了长度可变的数组 • 优点遍历元素和随机访问元素的效率比较高 • 缺点添加和删除需大量移动元素效率低按照内容查询效率低• LinkedList • 采用双向链表存储方式。 • 缺点遍历和随机访问元素效率低下 • 优点插入、删除元素效率比较高但是前提也是必须先低效率查询才可。如果插入删除发生在头尾可以减少查询次数ArrayList源码分析ArrayList底层就是一个长度可以动态增长的Object数组StringBuilder底层就是一个长度可以动态增长的char数组publicclassArrayListEextendsAbstractListEimplements
ListE, RandomAccess, Cloneable, Serializable{privatestaticfinalintDEFAULT_CAPACITY10;privatestaticfinalObject[] EMPTY_ELEMENTDATA {};privatestaticfinalObject[]
DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};transientObject[] elementData;privateintsize;
}JDK1.7中使用无参数构造方法创建ArrayList对象时默认底层数组长度是10。JDK1.8中使用无参数构造方法创建ArrayList对象时默认底层数组长度是0第一次添加元素容量不足就要进行扩容了。publicArrayList() {this.elementDataDEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
privatestaticintcalculateCapacity(Object[] elementData, intminCapacity) {if (elementDataDEFAULTCAPACITY_EMPTY_ELEMENTDATA) {returnMath.max(DEFAULT_CAPACITY, minCapacity);}returnminCapacity;
}容量不足时进行扩容默认扩容50%。如果扩容50%还不足容纳新增元素就扩容为能容纳新增元素的最小数量。privatevoidgrow(intminCapacity) {intoldCapacityelementData.length;intnewCapacityoldCapacity (oldCapacity1);if (newCapacity-minCapacity0)newCapacityminCapacity;if (newCapacity-MAX_ARRAY_SIZE0)newCapacityhugeCapacity(minCapacity); elementDataArrays.copyOf(elementData, newCapacity);
}ArrayList中提供了一个内部类Itr实现了Iterator接口实现对集合元素的遍历publicIteratorEiterator() {returnnewItr();
}
privateclassItrimplementsIteratorE {
}LinkedList问题1将ArrayList替换成LinkedList之后不变的是什么² 运算结果没有变² 执行的功能代码没有变 问题2将ArrayList替换成LinkedList之后变化的是什么² 底层的结构变了 ArrayList数组 LinkedList双向链表² 具体的执行过程变化了 list.add(2,99) ArrayList大量的后移元素 LinkedList不需要大量的移动元素修改节点的指向即可 问题3到底是使用ArrayList还是LinkedList² 根据使用场合而定² 大量的根据索引查询的操作大量的遍历操作按照索引0--n-1逐个查询一般建议使用ArrayList² 如果存在较多的添加、删除操作建议使用LinkedList问题4LinkedList增加了哪些方法² 增加了对添加、删除、获取首尾元素的方法² addFirst()、addLast()、removeFirst()、removeLast()、getFirst()、getLast()、源码分析底层结构是一个双向链表。publicclassLinkedListEextendsAbstractSequentialListEimplementsListE, DequeE, Cloneable, java.io.Serializable{transientintsize0;//节点的数量transientNodeEfirst; //指向第一个节点transientNodeElast; //指向最后一个节点publicLinkedList() { }}有一个静态内部类Node表示双向链表的节点。privatestaticclassNodeE {Eitem;//存储节点的数据NodeEnext;//指向后一个节点NodeEprev; //指向前一个节点Node(NodeEprev, Eelement, NodeEnext) {this.itemelement;this.nextnext;this.prevprev;}
}LinkedList实现了Deque接口所以除了可以作为线性表来使用外还可以当做队列和栈来使用Java中栈和队列的实现类public class StackE extends VectorE Vector过时了被ArrayList替代了Stack也就过时了public interface QueueE extends CollectionE 接口public interface DequeE extends QueueE 接口Deque和Queue的实现类 ArrayDeque 顺序栈 数组 LinkedList 链栈 链表 Set集合• Set• 特点无序 唯一不重复实现类:• HashSet •采用Hashtable哈希表存储结构神奇的结构 •优点添加速度快 查询速度快 删除速度快 •缺点无序 • LinkedHashSet •采用哈希表存储结构同时使用链表维护次序 •缺点有序添加顺序• TreeSet •采用二叉树红黑树的存储结构 •优点有序 查询速度比List快按照内容查询 •缺点查询速度没有HashSet快HashSet 哈希表 唯一 无序 LinkedHashSet 哈希表链表 唯一 有序添加顺序 TreeSet 红黑树 一种二叉平衡树 唯一 有序自然顺序 List针对Collection增加了一些关于索引位置操作的方法 get(i) add(i,elem),remove(i),set(i,elem) Set是无序的不可能提供关于索引位置操作的方法set针对Collection没有增加任何方法List的遍历方式for循环、for-each循环、Iterator迭代器、流式编程forEachlSet的遍历方式 for-each循环、Iterator迭代器、流式编程forEachHashSet// TODO: 2022/8/12 HashSet保证唯一性--equals和hashCode
publicclassSetDemo1 {publicstaticvoidmain(String[] args) {SetStudentsetnewHashSet();set.add(newStudent(mark,19));set.add(newStudent(mark,19));System.out.println(set);}
}publicclassStudentimplementsComparableStudent{privateStringname;privateIntegerid;
Overridepublicbooleanequals(Objecto) {if (thiso) returntrue;if (onull||getClass() !o.getClass()) returnfalse;Studentstudent (Student) o;returnObjects.equals(name, student.name) Objects.equals(id, student.id);}
OverridepublicinthashCode() {returnObjects.hash(name, id);}TreeSet// TODO: 2022/8/12 treeSet保证唯一性--comparable接口 compareto外部比较器
public class SetDemo2 {public static void main(String[] args) {SetStudentsetnew TreeSet();set.add(new Student(mark,19));set.add(new Student(mayun,49));SetTeacherset2new TreeSet(new MyCompareto());set2.add(new Teacher(mark,19));set2.add(new Teacher(mayun,49));}
}public class MyCompareto implements ComparatorTeacher {Overridepublic int compare(Teacher o1, Teacher o2) {return o1.getId()-o2.getId();}
}Iterator迭代器Iterator专门为遍历集合而生集合并没有提供专门的遍历的方法 Iterator实际是迭代器设计模式的实现Iterator的常用方法boolean hasNext(): 判断是否存在另一个可访问的元素 Object next(): 返回要访问的下一个元素void remove(): 删除上次访问返回的对象。哪些集合可以使用Iterator遍历层次1Collection、List、Set可以、Map不可以层次2提供iterator()方法的就可以将元素交给Iterator;层次3实现Iterable接口的集合类都可以使用迭代器遍历for-each循环和Iterator的联系for-each循环(遍历集合)时底层使用的是Iterator凡是可以使用for-each循环(遍历的集合)肯定也可以使用Iterator进行遍历for-each循环和Iterator的区别for-each还能遍历数组Iterator只能遍历集合使用for-each遍历集合时不能删除元素会抛出异常ConcurrentModificationException使用Iterator遍历合时能删除元素Iterator是一个接口它的实现类在哪里在相应的集合实现类中 ,比如在ArrayList中存在一个内部了Itr implements Iterator为什么Iterator不设计成一个类而是一个接口不同的集合类底层结构不同迭代的方式不同所以提供一个接口让相应的实现类来实现Collections工具类•关于集合操作的工具类好比ArraysMath •唯一的构造方法private不允许在类的外部创建对象 •提供了大量的static方法可以通过类名直接调用Collections简化集合操作ListIntegerlistnew ArrayList();Collections.addAll(list,8,1,4,7,1,2,6,4,0);
System.out.println(list);
System.out.println();
Collections.sort(list);
System.out.println(list);System.out.println();Collections.sort(list,(t1,t2)-t2-t1);
System.out.println(list);System.out.println();Integer max Collections.max(list);
Integer min Collections.min(list);
System.out.println(max min);
System.out.println();
//填充
Collections.fill(list,1);
System.out.println(list);System.out.println();
ListIntegerlist1new ArrayList();
Collections.addAll(list1,6,3,0,3,0,5,1,3,6,99,99);
Collections.copy(list1,list);
System.out.println(list);
System.out.println(list1);System.out.println();
//变成性能安全
ListInteger list2 Collections.synchronizedList(list1);
System.out.println(list2);Stream流public static void main(String[] args) {ListInteger listnew ArrayList();Collections.addAll(list,8,1,4,7,1,2,6,4,0);System.out.println();System.out.println(list.stream().max((t1, t2) --1 ).get());System.out.println();list.stream().filter(t-t2).forEach(t- System.out.println(t));System.out.println();ListIntegerlist2new ArrayList();list.stream().filter(t-t5).forEach(t-list2.add(t));System.out.println(list2);
}线程安全类线程安全集合类可以分为三大类遗留的线程安全集合如 Hashtable Vector使用 Collections 装饰的线程安全集合如Collections.synchronizedCollectionCollections.synchronizedListCollections.synchronizedMapCollections.synchronizedSetCollections.synchronizedNavigableMapCollections.synchronizedNavigableSetCollections.synchronizedSortedMapCollections.synchronizedSortedSetjava.util.concurrent.*重点介绍 java.util.concurrent.* 下的线程安全集合类可以发现它们有规律里面包含三类关键词Blocking、CopyOnWrite、ConcurrentBlocking 大部分实现基于锁并提供用来阻塞的方法CopyOnWrite 之类的容器修改开销相对较重Concurrent 类型的容器内部很多操作使用 cas 优化一般可以提供较高吞吐量弱一致性遍历时弱一致性例如当利用迭代器遍历时如果容器发生修改迭代器仍然可以继续进行遍历这时内容是旧的求大小弱一致性size 操作未必是 100% 准确读取弱一致性遍历时如果发生了修改对于非安全容器来讲使用 fail-fast 机制也就是让遍历立刻失败抛出ConcurrentModificationException不再继续遍历HashMap引入哈希表哈希表是如何添加数据的 1) 计算哈希 码(调用hashCode(),结果是一个int值整数的哈希码取自身即可) 2) 计算在哈希表中的存储位置 yk(x)x%11 x:哈希码 k(x) 函数y在哈希表中的存储位置 3) 存入哈希表 n 情况1一次添加成功 n 情况2多次添加成功出现了冲突调用equals()和对应链表的元素进行比较比较到最后结果都是false创建新节点存储数据并加入链表末尾 n 情况3不添加出现了冲突调用equals()和对应链表的元素进行比较 经过一次或者多次比较后结果是true表明重复不添加 结论1哈希表添加数据快3步即可不考虑冲突 结论2唯一、无序 hashCode和equals到底有什么神奇的作用² hashCode():计算哈希码是一个整数根据哈希码可以计算出数据在哈希表中的存储位置 ² equals()添加时出现了冲突需要通过equals进行比较判断是否相同查询时也需要使用equals进行比较判断是否相同 如何减少冲突 哈希表的长度和表中的记录数的比例--装填因子 如果Hash表的空间远远大于最后实际存储的记录个数则造成了很大的空间浪费 如果选取小了的话则容易造成冲突。 在实际情况中一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数则需要动态维护Hash表的容量此时可能需要重新计算Hash地址。 装填因子表中的记录数/哈希表的长度 4/ 16 0.25 8/ 160.5 如果装填因子越小表明表中还有很多的空单元则添加发生冲突的可能性越小而装填因子越大则发生冲突的可能性就越大在查找时所耗费的时间就越多。 有相关文献证明当装填因子在0.5左右时候Hash性能能够达到最优。 因此一般情况下装填因子取经验值0.5。 2哈希函数的选择 直接定址法 平方取中法 折叠法 除留取余法y x%11 3处理冲突的方法 链地址法 开放地址法 再散列法 建立一个公共溢出区JDK1.7 HashMap•JDK1.7及其之前HashMap底层是一个table数组链表实现的哈希表存储结构 •链表的每个节点就是一个Entry其中包括键key、值value、键的哈希码hash、执行下一个节点的引用next四部分static class EntryK, V implements Map.EntryK, V {final K key; //keyV value;//valueEntryK, V next; //指向下一个节点的指针int hash;//哈希码
}JDK1.7中HashMap的主要成员变量及其含义public class HashMapK, V implements MapK, V {
//哈希表主数组的默认长度static final int DEFAULT_INITIAL_CAPACITY 16;
//默认的装填因子static final float DEFAULT_LOAD_FACTOR 0.75f;
//主数组的引用transient EntryK, V[] table; int threshold;//界限值 阈值final float loadFactor;//装填因子//无参构造public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}//有参构造.public HashMap(int initialCapacity, float loadFactor) {this.loadFactor loadFactor;//0.75threshold (int) Math.min(capacity * loadFactor,
MAXIMUM_CAPACITY 1);//16*0.7512table new Entry[capacity];....}
}put方法•调用put方法添加键值对。哈希表三步添加数据原理的具体实现是计算key的哈希码和value无关。特别注意第一步计算哈希码时不仅调用了key的hashCode()还进行了更复杂处理目的是尽量保证不同的key尽量得到不同的哈希码第二步根据哈希码计算存储位置时使用了位运算提高效率。同时也要求主数组长度必须是2的幂第三步添加Entry时添加到链表的第一个位置而不是链表末尾第三步添加Entry是发现了相同的key已经存在就使用新的value替代旧的value并且返回旧的valuepublic class HashMap {//put方法public V put(K key, V value) {//如果key是null特殊处理if (key null) return putForNullKey(value);//1.计算key的哈希码hash int hash hash(key);//2.将哈希码代入函数计算出存储位置 y x%16int i indexFor(hash, table.length);//如果已经存在链表判断是否存在该key需要用到equals()for (EntryK,V e table[i]; e ! null; e e.next) {Object k;//如找到了,使用新value覆盖旧的value返回旧valueif (e.hash hash ((k e.key) key || key.equals(k))) { V oldValue e.value;// the United Statese.value value;//Americae.recordAccess(this);return oldValue;}}//上面循环走完没有找到这个节点说明该链表头都没有添加一个结点addEntry(hash, key, value, i);return null;}
final int hash(Object k) {int h 0;h ^ k.hashCode();h ^ (h 20) ^ (h 12);return h ^ (h 7) ^ (h 4);
}
static int indexFor(int h, int length) {
//作用就相当于y x%16,采用了位运算效率更高return h (length-1);}
}添加元素时如达到了阈值需扩容每次扩容为原来主数组容量的2倍void addEntry(int hash, K key, V value, int bucketIndex) {//如果达到了门槛值就扩容容量为原来容量的2位 16---32if ((size threshold) (null ! table[bucketIndex])) {resize(2 * table.length);hash (null ! key) ? hash(key) : 0;bucketIndex indexFor(hash, table.length);}//添加节点createEntry(hash, key, value, bucketIndex);
}扩容时jdk1.7的链表添加是采用头插法于是会出现数据的顺序颠倒的情况void resize(int newCapacity) {//resize(2 * table.length);Entry[] oldTable table;int oldCapacity oldTable.length;//得到旧值(主数组长度)if (oldCapacity MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return;}Entry[] newTable new Entry[newCapacity];//新长度为原来的两倍boolean oldAltHashing useAltHashing;useAltHashing | sun.misc.VM.isBooted() (newCapacity Holder.ALTERNATIVE_HASHING_THRESHOLD);boolean rehash oldAltHashing ^ useAltHashing;transfer(newTable, rehash);//进入transfer方法---重点 table newTable;threshold (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1);
}void transfer(Entry[] newTable, boolean rehash) {//将扩容完的主数组传过来int newCapacity newTable.length;for (EntryK,V e : table) {while(null ! e) {EntryK,V next e.next;if (rehash) {e.hash null e.key ? 0 : hash(e.key);//重新hash}int i indexFor(e.hash, newCapacity);//计算数组下标//头插开始--------------------------------------e.next newTable[i];newTable[i] e;//头插结束--------------------------------------e next;//接着遍历}}}get方法•调用get方法根据key获取value。 • 哈希表三步查询数据原理的具体实现 • 其实是根据key找Entry再从Entry中获取value即可public V get(Object key) {//根据key找到EntryEntry中有key和valueEntryK,V entry getEntry(key);//如果entry null,返回null否则返回valuereturn null entry ? null : entry.getValue();
}
final EntryK,V getEntry(Object key) {int hash (key null) ? 0 : hash(key);for (EntryK,V e table[indexFor(hash, table.length)];e ! null;e e.next) {Object k;if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;}return null;
}JDK1.7死链问题从transfer方法可以看到链表插入仍然是采用了头插法。这也就导致了有可能在多线程的情况下发生循环链表的现象。条件一 有两个线程A和B条件二: 此时在某个链表上面存在两个结点1和2并且这两个结点经过rehash仍然在同一结点链表上面条件三: 此时线程A走到tranfer里并且刚好停留在刚刚拿到Entry e结点1的代码,同时线程B也在transfer里面并且它率先完成了扩容!此时链表里面变成了 2 - 1条件四: 线程A刚好恢复运行 它又把结点1插入新的位置它将新位置设置成自己的next但是此时新位置上面放的是结点2 然后让新位置设置成自己然后接着遍历此时next已经是结点2然而结点2的next却是结点1所以造成了循环链表。JDK1.8 HashMap看源码:HashMap的一些成员变量public class HashMapK,V extends AbstractMapK,Vimplements MapK,V, Cloneable, Serializable {private static final long serialVersionUID 362498820763181265L;static final int DEFAULT_INITIAL_CAPACITY 1 4; // 默认容量16static final int MAXIMUM_CAPACITY 1 30; //最大容量2^30static final float DEFAULT_LOAD_FACTOR 0.75f; //装填因子0.75static final int TREEIFY_THRESHOLD 8; //是否树化的阈值: 链表长度大于等于8static final int UNTREEIFY_THRESHOLD 6; //是否退树的阈值: 链表长度小于等于6static final int MIN_TREEIFY_CAPACITY 64; //最小树化容量: 64// 构造方法:懒惰初始化仅仅将容量以及阈值赋值并不真正创建主数组对象。
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {//将容量和装填因子填充if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor;this.threshold tableSizeFor(initialCapacity);
}public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // 仅仅是赋值装填因子
}public HashMap(Map? extends K, ? extends V m) {this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}
node结点的结构:
static class NodeK,V implements Map.EntryK,V {final int hash; //哈希值final K key; //keyV value; //vNodeK,V next; //下一节点
}put方法hashMap的put写入数据的具体流程?首先要通过扰动函数计算出更加散列的hash值进入到putVal方法判断当前散列表数组是否为空如果为空那么就创建散列表默认数组的长度为16假如说有指定数组的长度这个长度会让tableSizeFor给被转化为2的次幂。用这个哈希值跟数组(散列表数组)的长度-1做与运算计算出即将插入散列表的下标值然后检查这个位置上面是否为空如果为空直接插入如果不为空检查key是否一样如果一样则直接替换。否则会判断这个位置是否为红黑树如果是的话就以红黑树的put插入否则遍历链表如果链表中有相同的key那么直接替换否则添加到最后(1.7是头插)如果插入之后长度超过8那么会进入树化操作假如说当前散列表数组没有达到树化条件长度未超过64那么会直接扩容否则将链表转化为红黑树。插入值成功后将modCount自增最后size自增。检查是否可以扩容如果可以那么就扩容。也就是说我们关注的put操作里面最重要的两个: 扩容与树化发生的时机为当链表长度达到一定的阈值(默认为8)时会进入树化操作。 此时如果哈希表的size已经达到了64那么会直接树化。如果未达到64那么会进行扩容最后put成功后size自增也会检查是否可以扩容。源码 public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;//在这里完成第一次主数组的初始化if ((p tab[i (n - 1) hash]) null)//如果插入位置是头结点tab[i] newNode(hash, key, value, null);//新建头结点else {//不是头结点-----------------------------//要么就插到链表尾部要么就是插入红黑树NodeK,V e; K k;//---------------------------------------整体if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;//如果进来第一个就是直接拿到这个结点(需要替换)else if (p instanceof TreeNode)//如果当前结点已经是红黑树//放入红黑树,执行红黑树的put结点e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {//否则说明在链表里面需要遍历链表for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//如果达到了树化的条件则转成红黑树break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}//---------------------------------------整体if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)//如果当前数组大小已经超过阈值,那么需要扩容resize();afterNodeInsertion(evict);return null;}红黑树的put结点final TreeNodeK,V putTreeVal(HashMapK,V map, NodeK,V[] tab,int h, K k, V v) {Class? kc null;boolean searched false;TreeNodeK,V root (parent ! null) ? root() : this;for (TreeNodeK,V p root;;) {int dir, ph; K pk;//----------------------------------------------整体if ((ph p.hash) h)dir -1;else if (ph h)dir 1;else if ((pk p.key) k || (k ! null k.equals(pk)))return p;else if ((kc null (kc comparableClassFor(k)) null) ||(dir compareComparables(kc, k, pk)) 0) {if (!searched) {TreeNodeK,V q, ch;searched true;if (((ch p.left) ! null (q ch.find(h, k, kc)) ! null) ||((ch p.right) ! null (q ch.find(h, k, kc)) ! null))return q;}dir tieBreakOrder(k, pk);}//----------------------------------------------整体TreeNodeK,V xp p;if ((p (dir 0) ? p.left : p.right) null) {NodeK,V xpn xp.next;TreeNodeK,V x map.newTreeNode(h, k, v, xpn);if (dir 0)xp.left x;elsexp.right x;xp.next x;x.parent x.prev xp;if (xpn ! null)((TreeNodeK,V)xpn).prev x;moveRootToFront(tab, balanceInsertion(root, x));return null;}}
}树化treeifyBinfinal void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize();//如果当前表为空或者--》数组的长度未超过64只扩容不树化else if ((e tab[index (n - 1) hash]) ! null) {TreeNodeK,V hd null, tl null;do {TreeNodeK,V p replacementTreeNode(e, null);//转化成树结点-----------if (tl null)hd p;else {p.prev tl;tl.next p;}tl p;} while ((e e.next) ! null);//拼接成链表(树结点链表)if ((tab[index] hd) ! null)//将树结点链表赋给主数组hd.treeify(tab);//变成红黑树}
}扩容方法resizefinal NodeK,V[] resize() {NodeK,V[] oldTab table;int oldCap (oldTab null) ? 0 : oldTab.length;int oldThr threshold;int newCap, newThr 0;if (oldCap 0) {if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold}else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr 0) {float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold newThr;SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;if (oldTab ! null) {for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {oldTab[j] null;if (e.next null)newTab[e.hash (newCap - 1)] e;else if (e instanceof TreeNode)((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve orderNodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);if (loTail ! null) {loTail.next null;newTab[j] loHead;}if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;
}get方法public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;
}getNode方法要么就是直接在数组里要么就是链表要么就是红黑树。final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))return first;//首结点就是了不必遍历链表if ((e first.next) ! null) { //要么在链表里面要么在红黑树里if (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;//否则直接没找到返回空
}TreeMap红黑树特性1.二叉搜索树2.根节点为黑色3.红子为黑(红结点的孩子只能是黑色结点)则不可能存在连续的红色结点4.黑高相同(任一结点到叶子结点的路径上黑结点数量一致)5.null结点和叶子结点为黑色(不保证一定遵循)总的来说红黑树是一种特殊的平衡二叉搜索树它相对平衡树来说没有很频繁地进行平衡而是通过添加了相应的红黑规则来减少平衡的次数同时也能达到调整二叉树深度的效果红黑树插入结点时的情况(默认插入的新结点为红色结点)当前为根节点则直接插入父亲为黑色结点也可以直接插入父亲为红色结点3.叔结点也是为红色结点那么只需要变色并且往上递归。叔结点是黑色结点需要变色又旋转。分为四种情况4.新插入的结点和父结点都在右子树左旋转变色5.新插入的结点和父结点都在左子树右旋转变色6.新插入结点在左父结点在右右旋左旋7.新插入结点在右父结点在左左旋右旋源码private final Comparator? super K comparator; //外部比较器private transient EntryK,V root;//根节点Entrystatic final class EntryK,V implements Map.EntryK,V {K key;V value;EntryK,V left;EntryK,V right;EntryK,V parent;boolean color BLACK;Entry(K key, V value, EntryK,V parent) {this.key key;this.value value;this.parent parent;}public K getKey() {return key;}public V getValue() {return value;}public V setValue(V value) {V oldValue this.value;this.value value;return oldValue;}public boolean equals(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry?,? e (Map.Entry?,?)o;return valEquals(key,e.getKey()) valEquals(value,e.getValue());}public int hashCode() {int keyHash (keynull ? 0 : key.hashCode());int valueHash (valuenull ? 0 : value.hashCode());return keyHash ^ valueHash;}public String toString() {return key value;}
}put方法public V put(K key, V value) {EntryK,V t root;if (t null) {compare(key, key); //树的根节点为空则创建新的根节点root new Entry(key, value, null);size 1;modCount;return null;}//-------------------通过红黑树的特性来插入int cmp;EntryK,V parent;Comparator? super K cpr comparator;//---------------------------------通过对比大小找出插入结点该放的位置if (cpr ! null) {//如果是有自带外部比较器的话就用别人自带的do {parent t;cmp cpr.compare(key, t.key);if (cmp 0)t t.left;else if (cmp 0)t t.right;elsereturn t.setValue(value);} while (t ! null);}else {if (key null)throw new NullPointerException();SuppressWarnings(unchecked)Comparable? super K k (Comparable? super K) key;do {parent t;cmp k.compareTo(t.key);if (cmp 0)t t.left;else if (cmp 0)t t.right;elsereturn t.setValue(value);} while (t ! null);}
//---------------------------------通过对比大小找出插入结点该放的位置EntryK,V e new Entry(key, value, parent);//创建新的树结点if (cmp 0)parent.left e;elseparent.right e;fixAfterInsertion(e);//这个方法是调整红黑树为合理的红黑树(修复)size;modCount;return null;
}修复红黑树private void fixAfterInsertion(EntryK,V x) {x.color RED;while (x ! null x ! root x.parent.color RED) {if (parentOf(x) leftOf(parentOf(parentOf(x)))) {EntryK,V y rightOf(parentOf(parentOf(x)));if (colorOf(y) RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x parentOf(parentOf(x));} else {if (x rightOf(parentOf(x))) {x parentOf(x);rotateLeft(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));}} else {EntryK,V y leftOf(parentOf(parentOf(x)));if (colorOf(y) RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x parentOf(parentOf(x));} else {if (x leftOf(parentOf(x))) {x parentOf(x);rotateRight(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));}}}root.color BLACK;
}ConcurrentHashMap解决hashMap留下的线程安全问题——可以使用hashTable但是由于它大量使用synch,效率不太好。所以要使用并发度更高的concurrentHashMapjdk1.7的ConcurrentHashMap引入了分段锁。数据结构使用Segement数组hashEntry数组链表。segement继承reentrantLock一个segementp[i]就是一把锁锁的粒度更细性能更高了。一个Segement相当于一个锁它只锁住一个槽位其他的槽位不受影响。chm将hash表默认分为16个桶锁的时候只锁住当前需要用到的桶一开始的hashTable只能一个线程进入但是现在却可以16个线程同时进入并发性就得到了大大的提高。jdk1.8的时候做出了很大的改变数据结构采用node数组链表红黑树抛弃了segement分段锁采用了cassynch 锁的粒度更细只锁住链表头节点(红黑树root节点)不影响其他哈希表数组元素的读写再次提高了并发度。
