- 浏览: 148920 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
EclipseEye:
fair_jm 写道不错 蛮详细的 谢谢分享
SWT/JFace专题 --- SWT中Display和多线程 -
fair_jm:
不错 蛮详细的 谢谢分享
SWT/JFace专题 --- SWT中Display和多线程
Map
------
1.HashMap
2.LinkedHashMap
3.IdentityHashMap
4.WeakHashMap
5.TreeMap
6.EnumMap
7.ConcurrentHashMap
8.ConcurrentSkipListMap
--------------------------------------
--------EnumMap----------------------------------------
与枚举类型键一起使用的专用 Map 实现。枚举映射中所有键都必须来自单个枚举类型,该枚举类型在创建映射时显式或隐式地指定。枚举映射在内部表示为数组。此表示形式非常紧凑且高效。
枚举映射根据其键的自然顺序 来维护(该顺序是声明枚举常量的顺序)。在 collection 视图(keySet()、entrySet() 和 values())所返回的迭代器中反映了这一点。
eg.:
上面是一个简单的例子。由于EnumMap的具有枚举类型的特点,类型固定且枚举值的个数固定,所以EnumMap效率是比较高的,可以结合具体的应用(特别像例子中的那样,元素的个数较少且较固定时考虑使用EnumMap存储数据)
--------TreeMap------------------------------------------
TreeMap是一种支持排序的Map,其实现方式和HashMap有较大区别,是红黑树数据结构的实现。
它是一个典型的基于红黑树的实现,因此要求一定要有key比较的方法,要么传入Comparator实现,要么key对像实现Comparator接口。
---------------
TreeMap的删除操作的实现:
-----------------------------------------------------------------------
---------红黑树(R-B Tree)--------------------
红黑树:一种二叉查找树(Binary Search Tree),但在每个结点上增加一个存储位表示结点的颜色(Red or Black)
通过对任何一条从根到叶子的路径上各个结点着色方式的限制,使得:
--红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。
--红黑树能保证在最坏的情况下,基本的动态几何操作的时间均为O(lgn)
*红黑树上每个结点内含有5个域:color、key、left、right、Entry。
*红黑树满足以下条件:(黑头,黑尾,两红不相挨)
----每个结点要么红的,要么黑的
----根结点是黑的
----每个叶子结点,即空结点(NULL)是黑的
----如果结点是红的,那么它的两个儿子都是黑的
----对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点
对于给定的黑色高度为 N 的红黑树,从根到叶子节点的最短路径长度为 N-1,最长路径长度为 2 * (N-1)
红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高,这样保证红黑树在最坏情况下都是高效的,不会出现普通排序二叉树的最坏的情况(插入数据时的有序情况下导致的)。
另外上面TreeMap中蓝色的注释部分,其实表示的就是红黑树在插入和删除元素时的修复情况。
网上有很多关于红黑树的详细解析,这里也就不再做过多的解释了。
关于红黑树的介绍 推荐:
http://blog.csdn.net/v_JULY_v/article/details/6105630
------------------------------------
------
1.HashMap
2.LinkedHashMap
3.IdentityHashMap
4.WeakHashMap
5.TreeMap
6.EnumMap
7.ConcurrentHashMap
8.ConcurrentSkipListMap
--------------------------------------
--------EnumMap----------------------------------------
public class EnumMap<K extends Enum<K>,V> extends AbstractMap<K,V> implements Serializable, Cloneable
与枚举类型键一起使用的专用 Map 实现。枚举映射中所有键都必须来自单个枚举类型,该枚举类型在创建映射时显式或隐式地指定。枚举映射在内部表示为数组。此表示形式非常紧凑且高效。
枚举映射根据其键的自然顺序 来维护(该顺序是声明枚举常量的顺序)。在 collection 视图(keySet()、entrySet() 和 values())所返回的迭代器中反映了这一点。
eg.:
import java.util.EnumMap; enum WeekEnum { Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday } public class EnumMapTest { private EnumMap<WeekEnum, String> enumMap = new EnumMap<WeekEnum, String>(WeekEnum.class); public EnumMapTest() { enumMap.put(WeekEnum.Monday, "星期一,一周开始"); enumMap.put(WeekEnum.Thursday, "星期二,一周第二天"); enumMap.put(WeekEnum.Wednesday, "星期三,好好工作……"); enumMap.put(WeekEnum.Thursday, "星期四,……"); enumMap.put(WeekEnum.Friday, "星期五,……"); enumMap.put(WeekEnum.Saturday, "星期六,……"); enumMap.put(WeekEnum.Sunday, "星期天,休息一下……"); } public String getDayDescription(WeekEnum day) { return this.enumMap.get(day); } public static void main(String[] args) { String dayDesc=new EnumMapTest().enumMap.get(WeekEnum.Sunday); System.err.println(dayDesc); } }
上面是一个简单的例子。由于EnumMap的具有枚举类型的特点,类型固定且枚举值的个数固定,所以EnumMap效率是比较高的,可以结合具体的应用(特别像例子中的那样,元素的个数较少且较固定时考虑使用EnumMap存储数据)
--------TreeMap------------------------------------------
TreeMap是一种支持排序的Map,其实现方式和HashMap有较大区别,是红黑树数据结构的实现。
/** *TreeMap中节点的存储结构 */ static final class Entry<K,V> implements Map.Entry<K,V> { /**6个变量域:键、值对、左、右兄弟、父节点、颜色属性 */ K key; V value; Entry<K,V> left = null;// Entry<K,V> right = null; Entry<K,V> parent; boolean color = BLACK; ...... }
put(Object key,Object value):
它是一个典型的基于红黑树的实现,因此要求一定要有key比较的方法,要么传入Comparator实现,要么key对像实现Comparator接口。
/** *通过“键值对”初始化Entry并把该Entry放到红黑树结构中(如果该key对应的Entry存在,其value就替换为新的value) */ public V put(K key, V value) { //临时变量t指向根节点 Entry<K,V> t = root; //如果t为空,也就是root为空,TreeMap是空链的情况下,根据键值对创建Entry,并将其置为root根节点 if (t == null) { root = new Entry<K,V>(key, value, null);//父节点为null size = 1;//size表示节点的个数 modCount++;//modCount表示链表的变化次数 return null; } int cmp; Entry<K,V> parent; /** *根据"比较器"comparator为null与否,采取定制比较或默认比较(key的Comparable)不同的方式 *然后,按照"二叉排序树"的方式从根节点开始查找。如果找到了就覆盖旧的value,并返回旧的value。 */ 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; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); 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; else return t.setValue(value); } while (t != null); } /** *如果上述遍历没有找到对应的key,则把key-value和最后的遍历得到的parent(也就是待插入位置的parent) *构造成新的Entry,作为新的插入节点。 */ Entry<K,V> e = new Entry<K,V>(key, value, parent); //设置parent和该新节点的关系 if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e);//插入新节点后,可能会改变原有的红黑树结构,要进行修复 size++; modCount++; return null; } /** 红黑树插入后修复算法(该算法来源于CLR--算法3作者的姓氏第一个字母) */ private void fixAfterInsertion(Entry<K,V> x) { //默认新插入的节点颜色为红色(这是为了尽量不改变红黑树黑节点的个数,具体可以查看"红黑树"的属性) x.color = RED; /** 直到 x 节点的父节点不是根,且 x 的父节点不是红色 (由于当x的父亲节点是黑色节点的时候,直接插入不会影响到红黑树的性质,所有就没有必要进行下面的操作了, 所以插入时,只考虑其父亲节点为红色的情况,只有这种情况下红黑树才需要修复操作)*/ while (x != null && x != root && x.parent.color == RED) { /** *新插入节点x的父节点为红色的时候又分为一下几种情况: *1 x 的父节点P是其父节点G的左子节点: *1.1 x的父亲节点p的兄弟节点为红色.解决办法:父设黑,父的兄设黑,父的父设红并以父的父为新节点往上遍历直到root涂黑。 *1.2 x的父亲节点p的兄弟节点为黑色.(此时,又分x是其父的左和右孩子两种情况) * 1.2.1 x是其父右子。解决办法: x变黑,父的父变红,父左旋转,父的父右旋转。 * 1.2.2 x是其父左子。解决办法:父变黑,父的父变红, 父的父右旋转, * *2 x 的父节点P是其父节点G的右子节点(道理同上) */ // 1 如果 x 的父节点P是其父节点G的左子节点 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { Entry<K,V> y = rightOf(parentOf(parentOf(x))); //1.1 如果x的父亲节点p的兄弟节点为红色 if (colorOf(y) == RED) { setColor(parentOf(x), BLACK);//将x的父亲节点设为黑色 setColor(y, BLACK); //将x的父亲节点兄弟节点设为黑色 setColor(parentOf(parentOf(x)), RED);//将x的父亲节点的父亲节点设为红色 x = parentOf(parentOf(x)); //将x设为其父亲节点的父亲节点,以便继续往上遍历 } else {//1.2 如果x的父亲节点p的兄弟节点为黑色 if (x == rightOf(parentOf(x))) {//1.2.1 下面左转的目的是变成1.2.2的情况 x = parentOf(x);//x指向其父 rotateLeft(x); //当前的x指向左旋转 } //1.2.2情况的处理 setColor(parentOf(x), BLACK); //父设黑 setColor(parentOf(parentOf(x)), RED);//父父设红 rotateRight(parentOf(parentOf(x)));//父父右旋转 } } else {//2 道理同上,只是出现right的地方换成了left,出现left的地方换成了right Entry<K,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根节点置黑,以满足“红黑树”黑头黑尾的性质。 root.color = BLACK; }
---------------
TreeMap的删除操作的实现:
private void deleteEntry(Entry<K,V> p) { modCount++; //修改次数加1 size--; //节点个数减1 // 如果被删除节点的左子树、右子树都不为空 if (p.left != null && p.right != null) { // 用 p 节点的中序后继节点代替 p 节点 Entry<K,V> s = successor (p); p.key = s.key; p.value = s.value; p = s; } /** *经过上面的操作(用 p 节点的中序后继节点代替 p 节点),实际要执行的删除操作就 *变成了针对p的中序后继节点(如果存在的话)的操作: *既然要删除的节点是后继节点,那么要删除的节点的左子树一定为空,所以: * 1 当(删除的节点)p为黑色时就有两种情况: * 1.1 p的左右均为null; * 1.2 p的左为空,右子树为一单个红色节点(并且该红色节点的左右为null,如果不为空就不会满足红黑树的性质了) * 2 当p为红色时:其左右子树比为null(也只有这样才能满足红黑树的性质) */ // 如果 p 节点的左节点存在,replacement 代表左节点;否则代表右节点。 Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) { //1.2的情况 replacement.parent = p.parent; // 如果 p 没有父节点,则 replacemment 变成父节点 if (p.parent == null) root = replacement; // 如果 p 节点是其父节点的左子节点,则把其父左设为replacement else if (p == p.parent.left) p.parent.left = replacement; // 如果 p 节点是其父节点的右子节点,则把其父右设为replacement else p.parent.right = replacement; p.left = p.right = p.parent = null; // 由于当p是红色节点时,直接删除后不会影响到红黑树的高度,所以就不用修复,当为黑节点时需修复红黑树 if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { // 如果 p 节点没有父节点,置为空链 root = null; } else { 1.1或2的情况:即要删除的p节点的左右子树均为null if (p.color == BLACK) //如果是p为黑色,就进行修复(红色时不必) // 修复红黑树 fixAfterDeletion(p); if (p.parent != null) { //在p父不为空的情况下,对其父的左(或右)节点进行删除后的置空处理 // 如果 p 是其父节点的左子节点 if (p == p.parent.left) p.parent.left = null; // 如果 p 是其父节点的右子节点 else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } ------ // 删除节点后修复红黑树 private void fixAfterDeletion(Entry<K,V> x) { /** *由于x为红的情况不存在修复的情况,所以 *当x为黑色是修复存在如下情况: *1 x 是其父节点的左子节点 * 1.1 当删除的节点有一个红孩子时。解决办法:红孩子目前属于删除节点父的一个孩子,把该孩子变成黑色。 * 1.2 当删除的节点左右子为null的情况下: * 1.2.1 删除节点的兄弟节点为红色。解决办法:父变红,兄变黑,父左旋转。 * 1.2.2 删除节点的兄弟节点为黑色。(又有多种情况) * 1.2.2.1 兄有两个黑子节点。解决办法:兄变红,子变黑,红父时变黑(黑父时,从黑父往上遍历) * 1.2.2.2 兄的子节点左黑右红。解决办法:兄变父色,父变黑,兄红子变黑,父左旋转。 * 1.2.2.3 兄的子节点左红右黑。解决办法:兄红子变父色,父变黑,兄右旋转,父左旋转。 *2 x 是其父节点的右子节点(道理同上) */ // 直到 x 不是根节点,且 x 的颜色是黑色 while (x != root && colorOf(x) == BLACK) { // 如果 x 是其父节点的左子节点 if (x == leftOf(parentOf(x))) { //1 情况 // 获取 x 节点的兄弟节点 Entry<K,V> sib = rightOf(parentOf(x)); // 如果 sib 节点是红色 if (colorOf(sib) == RED) { //1.2.1 情况 // 将 sib 节点设为黑色 setColor(sib, BLACK); // 将 x 的父节点设为红色 setColor(parentOf(x), RED); rotateLeft(parentOf(x)); // 再次将 sib 设为 x 的父节点的右子节点 sib = rightOf(parentOf(x)); } // 如果 sib 的两个子节点都是黑色 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 1.2.2.1 情况 // 将 sib 设为红色 setColor(sib, RED); // 让 x 等于 x 的父节点,继续遍历 x = parentOf(x); } else { // 如果 sib 的只有右子节点是黑色 if (colorOf(rightOf(sib)) == BLACK) { // 1.2.2.3 情况,下面几行操作是先将其转换成1.2.2.2的情况 // 将 sib 的左子节点也设为黑色 setColor(leftOf(sib), BLACK); // 将 sib 设为红色 setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } // 1.2.2.2 情况 // 设置 sib 的颜色与 x 的父节点的颜色相同 setColor(sib, colorOf(parentOf(x))); // 将 x 的父节点设为黑色 setColor(parentOf(x), BLACK); // 将 sib 的右子节点设为黑色 setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } else { // 2情况(道理同上) // 获取 x 节点的兄弟节点 Entry<K,V> sib = leftOf(parentOf(x)); // 如果 sib 的颜色是红色 if (colorOf(sib) == RED) { // 将 sib 的颜色设为黑色 setColor(sib, BLACK); // 将 sib 的父节点设为红色 setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } // 如果 sib 的两个子节点都是黑色 if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { // 将 sib 设为红色 setColor(sib, RED); // 让 x 等于 x 的父节点 x = parentOf(x); } else { // 如果 sib 只有左子节点是黑色 if (colorOf(leftOf(sib)) == BLACK) { // 将 sib 的右子节点也设为黑色 setColor(rightOf(sib), BLACK); // 将 sib 设为红色 setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } // 将 sib 的颜色设为与 x 的父节点颜色相同 setColor(sib, colorOf(parentOf(x))); // 将 x 的父节点设为黑色 setColor(parentOf(x), BLACK); // 将 sib 的左子节点设为黑色 setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } //最终设置root为黑色 setColor(x, BLACK); }
-----------------------------------------------------------------------
---------红黑树(R-B Tree)--------------------
红黑树:一种二叉查找树(Binary Search Tree),但在每个结点上增加一个存储位表示结点的颜色(Red or Black)
通过对任何一条从根到叶子的路径上各个结点着色方式的限制,使得:
--红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。
--红黑树能保证在最坏的情况下,基本的动态几何操作的时间均为O(lgn)
*红黑树上每个结点内含有5个域:color、key、left、right、Entry。
*红黑树满足以下条件:(黑头,黑尾,两红不相挨)
----每个结点要么红的,要么黑的
----根结点是黑的
----每个叶子结点,即空结点(NULL)是黑的
----如果结点是红的,那么它的两个儿子都是黑的
----对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点
对于给定的黑色高度为 N 的红黑树,从根到叶子节点的最短路径长度为 N-1,最长路径长度为 2 * (N-1)
红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高,这样保证红黑树在最坏情况下都是高效的,不会出现普通排序二叉树的最坏的情况(插入数据时的有序情况下导致的)。
另外上面TreeMap中蓝色的注释部分,其实表示的就是红黑树在插入和删除元素时的修复情况。
网上有很多关于红黑树的详细解析,这里也就不再做过多的解释了。
关于红黑树的介绍 推荐:
http://blog.csdn.net/v_JULY_v/article/details/6105630
------------------------------------
发表评论
-
Nio Socket
2013-05-16 05:53 0asfda -
结合jdk源码解读,Error Exception
2013-05-10 04:00 0/* * @(#)Error.java 1.17 05/11 ... -
从不同的角度,重新审视class和interface
2013-05-07 03:40 0java开发中,对应class和interface的基本区别都 ... -
java.lang.Object
2013-05-07 03:35 0/* * @(#)Object.java 1.73 06/0 ... -
反射机制+类加载机制
2013-02-18 01:30 0反射机制+类加载机制 -
并发专题----使用开源软件Amino构建并发应用程序/多线程运行时分析工具MTRAT
2013-02-14 00:50 1368使用开源软件构建并发 ... -
并发专题 ---- 线程安全
2013-02-14 00:50 744线程安全 ================== ... -
并发专题 --- 锁
2013-02-14 00:50 802相比于synchronized,ReentrantLock 提 ... -
并发专题 ----(JMM)java内存模型
2013-02-14 00:50 534Java 内存模型 ------------ ... -
并发专题 ---java.util.concurrent 包
2013-02-13 02:26 1832java.util.concurrent 包 原 ... -
集合框架 Queue篇(8)---PriorityBlockingQueue、SynchronousQueue
2013-02-07 12:40 1301Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(7)---LinkedBlockingDeque
2013-02-07 12:40 849Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(6)---LinkedBlockingQueue
2013-02-07 12:39 826Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(5)---ArrayBlockingQueue
2013-02-06 10:39 698Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(4)---阻塞队列和生产者-消费者模式、DelayQueue
2013-02-06 10:39 989Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(3)---ConcurrentLinkedQueue
2013-02-06 10:38 1042Queue ------------ 1.ArrayDequ ... -
集合框架 Queue篇(2)---PriorityQueue
2013-02-06 10:38 826Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(1)---ArrayDeque
2013-02-06 10:38 925Queue ------------ 1.ArrayDeq ... -
集合框架 Set篇---HashSet、LinkedHashSet、TreeSet、CopyOnWriteArraySet、ConcurrentSkipList
2013-02-05 08:43 1474Set --------- 1.HashSet 2.Link ... -
集合框架 List篇(2)---CopyOnWriteArrayList
2013-02-05 08:43 839List ----------- 1.ArrayList(jd ...
相关推荐
7. **Java集合框架中的重要类和方法**:包括但不限于Collection、Set、List、Map、Iterator、EnumSet、EnumMap、SortedSet、NavigableSet、SortedMap、NavigableMap以及它们的实现类。 在Java集合框架的发展史上,...
常见的实现有`HashMap`(哈希表实现)、`Hashtable`(线程安全的哈希表实现)和`TreeMap`(红黑树实现,保证排序)。 3. **迭代器接口**: - `Iterator`:用于遍历集合中的元素,提供了`next()`和`remove()`等方法...
- **Map接口**:存储键值对的数据结构,HashMap(哈希表,无序)和TreeMap(红黑树,有序)是最常用的实现。 2. **泛型** 集合框架引入了泛型,允许在创建集合时指定元素类型,从而在编译时检查类型安全,避免了...
后者基于红黑树,保持元素排序。 - `HashMap` 和 `TreeMap`: 分别实现了 `Map` 接口,前者快速查找,后者保持键的排序。 - `Stack` 和 `Deque`: `Stack` 是 `Vector` 的子类,实现后进先出(LIFO)结构,而 `Deque...
- **TreeMap**:基于红黑树的Map实现,键按自然顺序或自定义比较器排序。 - **LinkedHashMap**:保持插入顺序或访问顺序的Map实现,适合需要保持元素顺序的情况。 3. **工具类:** - **Collections**:提供了一...
- `TreeMap`:基于红黑树实现,提供了排序的键值对,元素按照键的自然顺序或自定义比较器排序。 - `Hashtable`:线程安全的`Map`实现,类似于早期版本的`HashMap`,但不接受`null`键和值。 - `LinkedHashMap`:保留...
`Map`接口还有其他实现,如`TreeMap`,它基于红黑树,提供有序的键值对,`LinkedHashMap`保持插入顺序或访问顺序,`ConcurrentHashMap`则适用于多线程环境下的并发操作。 在实际应用中,选择哪种`Map`实现取决于...
- 使用红黑树实现的排序集合,不允许重复元素。 - 保持元素的自然顺序或根据提供的比较器进行排序。 - 添加、删除和查找操作的时间复杂度为O(log n)。 5. **EnumSet** - 专门用于枚举类型的集合,效率极高。 -...
- **TreeMap**: 基于红黑树,保证了键的有序性,插入、删除和查找的时间复杂度为O(log n)。 5. **枚举类型(Enum)**: - Java枚举是一种特殊的数据类型,用于定义一组有限的常量。它们可以包含方法和字段,与其他...
TreeMap基于红黑树实现,可以根据键的自然顺序或构造时提供的Comparator进行排序。HashMap和TreeMap都允许null键和多个null值,但性能不同。HashMap提供了更快速的插入和检索,而TreeMap则在保持元素有序时有优势。 ...
而TreeMap则基于红黑树,提供有序的键值对,支持根据键的自然排序或自定义比较器进行排序。 Java集合框架还包含了Queue(队列)、Deque(双端队列)、Stack(栈)等接口和实现,例如LinkedList可以作为双端队列使用...
- `TreeMap`:基于红黑树实现,键值对有序,支持排序和区间操作。 3. **泛型与类型安全**: Java集合框架广泛使用泛型来确保类型安全,避免了强制类型转换,并提高了代码可读性。 4. **迭代器与泛型迭代器**: ...
- 使用哈希表实现,包含数组+链表(或红黑树)。 - 默认初始容量为16,扩容时容量翻倍。 - 遍历方式:通常使用`Iterator`。 #### 四、HashTable与HashMap的区别 - **线程安全性**:`HashTable`是线程安全的,而`...
3. **TreeSet与TreeMap**:TreeSet和TreeMap都基于红黑树数据结构,它们维护了元素的排序顺序。TreeSet按照自然排序或自定义比较器进行排序,而TreeMap则根据键的自然排序或提供的比较器对键进行排序。 4. **Queue...
- `TreeSet` 和 `TreeMap`:基于红黑树的`Set`和`Map`,保证排序性,适合需要有序集合的情况。 3. **泛型**:Java集合框架广泛使用泛型,使得集合可以持有特定类型的对象,增强了类型安全性和代码可读性。 4. **...
深入学习`ArrayList`(基于数组的列表实现)、`LinkedList`(双向链表实现...集合)、`LinkedHashSet`(保持插入顺序的`HashSet`)、`TreeSet`(可排序的`Set`实现)、`HashMap`(散列表实现)、`LinkedHashMap`(保持...
`TreeMap`实现了`SortedMap`接口,内部是红黑树,保证了键的排序。 5. **迭代器(Iterator)**:用于遍历集合中的元素,`Iterator`接口提供了`hasNext()`和`next()`方法,分别检查和获取下一个元素。 6. **泛型...
TreeSet则基于红黑树,保证元素排序。 3. Queue接口:Queue接口表示一种FIFO(先进先出)的集合,提供了enqueue和dequeue操作。LinkedList也实现了Queue接口,此外,PriorityQueue提供了一种根据元素优先级排序的...