电脑知识|欧美黑人一区二区三区|软件|欧美黑人一级爽快片淫片高清|系统|欧美黑人狂野猛交老妇|数据库|服务器|编程开发|网络运营|知识问答|技术教程文章 - 好吧啦网

您的位置:首頁技術文章
文章詳情頁

Java基礎之TreeMap詳解

瀏覽:134日期:2022-08-13 11:51:59
一、寫在前面

TreeMap的底層數據結構是紅黑樹,且TreeMap可以實現集合元素的排序。

所以TreeMap的源碼需要實現:

1.紅黑樹的數據結構,以及紅黑樹的節點插入,刪除,以及紅黑樹的自平衡操作,如左旋,右旋,以及節點變色

2.紅黑樹需要支持按照指定的比較器進行排序,或者進行自然排序。

二、定義

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable

public interface NavigableMap<K,V> extends SortedMap<K,V> {

TreeMap

繼承了AbstractMap

實現了NavigableMap,而NavigableMap接口繼承了SortedMap接口,SortedMap接口表示其實現類是一個有序集合

實現了Cloneable,所以支持對象克隆

實現了Serializable,所以支持對象序列化

三、成員變量

comparator

/** * The comparator used to maintain order in this tree map, or * null if it uses the natural ordering of its keys. * * @serial */ private final Comparator<? super K> comparator;

外部指定的比較器。在創建TreeMap對象時可以指定。如果指定了比較器,則TreeMap插入鍵值對時,按照comparator比較排序。

root

private transient Entry<K,V> root;

root指代TreeMap底層紅黑樹的根節點。 root的類型Entry<K,V>就是紅黑樹節點的類型。

紅黑樹數據結構的實現就依賴于Entry<K,V>

size

/** * The number of entries in the tree */ private transient int size = 0;

表示TreeMap集合中鍵值對個數。

modCount

/** * The number of structural modifications to the tree. */ private transient int modCount = 0;

表示TreeMap集合被結構化修改的次數。用于迭代器迭代過程中檢測集合是否被結構化修改,若是,則fail-fast。

四、內部類

Entry<K,V>

Entry<K,V>是紅黑樹節點的代碼實現,是實現紅黑樹數據結構的基礎。

static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;Entry<K,V> left;Entry<K,V> right;Entry<K,V> parent;boolean color = BLACK; /** * Make a new cell with given key, value, and parent, and with * {@code null} child links, and BLACK color. */Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent;} /** * Returns the key. * * @return the key */public K getKey() { return key;} /** * Returns the value associated with the key. * * @return the value associated with the key */public V getValue() { return value;} /** * Replaces the value currently associated with the key with the given * value. * * @return the value associated with the key before this method was * called */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 = (key==null ? 0 : key.hashCode()); int valueHash = (value==null ? 0 : value.hashCode()); return keyHash ^ valueHash;} public String toString() { return key + '=' + value;} }

成員變量

K key,V value分別是TreeMap集合中存儲的鍵值對的鍵和值

Entry<K,V> left 代表當前節點的左子節點

Entry<K,V> right 代表當前節點的右子節點

Entry<K,V> parent 代表當前節點的父節點

boolean color 代表當前節點的顏色,默認是黑色,為true

構造器

Entry<K,V>只提供了一個構造器 Entry(K key, V value, Entry<K,V> parent)

即:創建一個紅黑樹節點,只需要指定其存儲的鍵值信息,以及其父節點引用。不需要指定左孩子和右孩子,以及顏色。

成員方法

提供了getKey()方法返回當前節點的key值。

提供了getValue(),setValue(V v)分別用于獲取Value,以及覆蓋Value后返回oldValue

重寫了equals()方法用于判斷兩個紅黑樹節點是否相同。邏輯是:兩個紅黑樹節點的key要么都為null,要么equals結果true,且,value要么都為null,要么equals結果為true。

重寫了hashCode()方法。

重寫了toString()方法。

五、構造器

public TreeMap()

public TreeMap() {comparator = null; }

無參構造器,即不指定比較器的構造器。

注意,此時插入集合的鍵值對的key的類型必須實現Comparable接口,即提供自然排序能力,否則會報錯類型轉換異常。

public TreeMap(Comparator<? super K> comparator)

public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator; }

指定比較器的構造器。

指定的比較器用于比較key,且comparator指定了泛型,即比較器比較的元素的類型必須是K或者K的父類類型。

public TreeMap(Map<? extends K, ? extends V> m)

public TreeMap(Map<? extends K, ? extends V> m) {comparator = null;putAll(m); }

將非TreeMap集合轉為TreeMap集合構造器

public TreeMap(SortedMap<K, ? extends V> m)

public TreeMap(SortedMap<K, ? extends V> m) {comparator = m.comparator();try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null);} catch (java.io.IOException cannotHappen) {} catch (ClassNotFoundException cannotHappen) {} }

將有序Map集合轉為TreeMap集合

六、成員方法

public V get(Object key)

public V get(Object key) {Entry<K,V> p = getEntry(key);return (p==null ? null : p.value); }

TreeMap的get方法用于獲取指定key的value。如果指定key沒有對應的紅黑樹節點,則返回null,否則返回對應紅黑樹節點的value。

可以看到get方法實現依賴于getEntry(Object key)方法。

getEntry(Object key)方法是根據指定key找對應的紅黑樹節點并返回該節點。

final Entry<K,V> getEntry(Object key)

final Entry<K,V> getEntry(Object key) {// Offload comparator-based version for sake of performanceif (comparator != null)//如果外部指定了比較器 return getEntryUsingComparator(key);//則使用指定比較器來查找if (key == null)//如果外部沒有指定比較器,且要查找的key為null,則拋出空指針異常 throw new NullPointerException();@SuppressWarnings('unchecked')//此時外部沒有指定構造器,且要查的Key不為null Comparable<? super K> k = (Comparable<? super K>) key;//檢查Key的類型是否實現了Comparable接口,即是否實現了自然排序,如果實現了,則此處可以強轉成功,否則會報錯類型轉換異常Entry<K,V> p = root;while (p != null) {//從紅黑樹根節點開始使用key本身的自然排序進行比較 int cmp = k.compareTo(p.key); if (cmp < 0)//如果要查找的key小于樹節點的key,則說明要找的key在當前節點的左子樹上,則下次遍歷從左子樹的根節點開始p = p.left; else if (cmp > 0)//如果要查找的key大于樹節點的key,則說明要找的key在當前節點的右子樹上,則下次遍歷從右子樹的根節點開始p = p.right; else//如果要查找的key等于樹節點的key,則該節點就是要找的,直接返回該節點return p;}return null;//如果上面遍歷沒有找到對應Key的節點,則返回null } final Entry<K,V> getEntryUsingComparator(Object key) {//使用指定比較器來查找,邏輯基本和自然排序查找一樣,只是這里使用了比較器排序查找@SuppressWarnings('unchecked') K k = (K) key;Comparator<? super K> cpr = comparator;if (cpr != null) { Entry<K,V> p = root; while (p != null) {int cmp = cpr.compare(k, p.key);if (cmp < 0) p = p.left;else if (cmp > 0) p = p.right;else return p; }}return null; }

Java基礎之TreeMap詳解

public V put(K key, V value)

public V put(K key, V value) {Entry<K,V> t = root;if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? 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(); @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;else return t.setValue(value); } while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0) parent.left = e;else parent.right = e;fixAfterInsertion(e);size++;modCount++;return null; }

final int compare(Object k1, Object k2) {return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2) : comparator.compare((K)k1, (K)k2); }

public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue;}

TreeMap的put方法用于插入一個鍵值對,

當插入的key在集合中不存在時,則put表示新增鍵值對,并返回null;

當插入的key在集合中存在時,則put表示覆蓋已存在key對應的value,并返回老value。

Java基礎之TreeMap詳解

private void fixAfterInsertion(Entry<K,V> x)

private void fixAfterInsertion(Entry<K,V> x) {//x是被插入的紅黑樹節點x.color = RED;//默認被插入的節點都是紅色 while (x != null && x != root && x.parent.color == RED) {//如果被插入節點不是根節點 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {Entry<K,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 {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.color = BLACK;//如果被插入的節點是根節點,則節點顏色改為黑色 }

fixAfterInsertion方法用于:當TreeMap插入紅黑樹節點后,導致紅黑樹不平衡時,TreeMap保持自平衡的自旋和變色操作。

該方法的入參就是插入的紅黑樹節點。

到此這篇關于Java基礎之TreeMap詳解的文章就介紹到這了,更多相關Java TreeMap詳解內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網!

標簽: Java
相關文章:
主站蜘蛛池模板: 【德信自动化】点胶机_全自动点胶机_自动点胶机厂家_塑料热压机_自动螺丝机-深圳市德信自动化设备有限公司 | 圆周直径尺-小孔内视镜-纤维研磨刷-东莞市高腾达精密工具 | 【ph计】|在线ph计|工业ph计|ph计厂家|ph计价格|酸度计生产厂家_武汉吉尔德科技有限公司 | 深圳工程师职称评定条件及流程_深圳职称评审_职称评审-职称网 | 屏蔽服(500kv-超高压-特高压-电磁)-徐吉电气 | 英国公司注册-新加坡公司注册-香港公司开户-离岸公司账户-杭州商标注册-杭州优创企业 | PSI渗透压仪,TPS酸度计,美国CHAI PCR仪,渗透压仪厂家_价格,微生物快速检测仪-华泰和合(北京)商贸有限公司 | 热处理温控箱,热处理控制箱厂家-吴江市兴达电热设备厂 | 电渗析,废酸回收,双极膜-山东天维膜技术有限公司 | 齿轮减速马达一体式_蜗轮蜗杆减速机配电机-德国BOSERL齿轮减速电动机生产厂家 | 单锥双螺旋混合机_双螺旋锥形混合机-无锡新洋设备科技有限公司 | 传动滚筒,改向滚筒-淄博建凯机械科技有限公司 | 爆破器材运输车|烟花爆竹运输车|1-9类危险品厢式运输车|湖北江南专用特种汽车有限公司 | 技德应用| 超声波焊接机_超音波熔接机_超声波塑焊机十大品牌_塑料超声波焊接设备厂家 | 圣才学习网-考研考证学习平台,提供万种考研考证电子书、题库、视频课程等考试资料 | 石磨面粉机|石磨面粉机械|石磨面粉机组|石磨面粉成套设备-河南成立粮油机械有限公司 | 示波器高压差分探头-国产电流探头厂家-南京桑润斯电子科技有限公司 | 净化车间_洁净厂房_净化公司_净化厂房_无尘室工程_洁净工程装修|改造|施工-深圳净化公司 | 深圳装修_店面装修设计_餐厅设计_装修全包价格-尚泰装饰设计 | 多物理场仿真软件_电磁仿真软件_EDA多物理场仿真软件 - 裕兴木兰 | 电动不锈钢套筒阀-球面偏置气动钟阀-三通换向阀止回阀-永嘉鸿宇阀门有限公司 | 档案密集柜_手动密集柜_智能密集柜_内蒙古档案密集柜-盛隆柜业内蒙古密集柜直销中心 | 帽子厂家_帽子工厂_帽子定做_义乌帽厂_帽厂_制帽厂 | 药品冷藏箱厂家_低温冰箱_洁净工作台-济南欧莱博电子商务有限公司官网 | 苏州防水公司_厂房屋面外墙防水_地下室卫生间防水堵漏-苏州伊诺尔防水工程有限公司 | 盛源真空泵|空压机-浙江盛源空压机制造有限公司-【盛源官网】 | 硬质合金模具_硬质合金非标定制_硬面加工「生产厂家」-西迪技术股份有限公司 | 一体化污水处理设备_生活污水处理设备_全自动加药装置厂家-明基环保 | 窖井盖锯圆机_锯圆机金刚石锯片-无锡茂达金刚石有限公司 | YAGEO国巨电容|贴片电阻|电容价格|三星代理商-深圳市巨优电子有限公司 | 锂电池砂磨机|石墨烯砂磨机|碳纳米管砂磨机-常州市奥能达机械设备有限公司 | 华中线缆有限公司-电缆厂|电缆厂家|电线电缆厂家 | 骨灰存放架|骨灰盒寄存架|骨灰架厂家|智慧殡葬|公墓陵园管理系统|网上祭奠|告别厅智能化-厦门慈愿科技 | 合金ICP光谱仪(磁性材料,工业废水)-百科 | 有声小说,听书,听小说资源库-听世界网| 山东聚盛新型材料有限公司-纳米防腐隔热彩铝板和纳米防腐隔热板以及钛锡板、PVDF氟膜板供应商 | Win10系统下载_32位/64位系统/专业版/纯净版下载 | 自动钻孔机-全自动数控钻孔机生产厂家-多米(广东)智能装备有限公司 | 色谱柱-淋洗液罐-巴罗克试剂槽-巴氏吸管-5ml样品瓶-SBS液氮冻存管-上海希言科学仪器有限公司 | 黄石妇科医院_黄石东方女子医院_黄石东方妇产医院怎么样 |