`
hz_chenwenbiao
  • 浏览: 996244 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

Java TreeMap的简单实现（转）

JavaITeyejunitBlog 
阅读更多

TreeMap的实现与二叉搜索树显示，其对应的节点格式为

Entry<K,V>   
Entry<K,V> left K key  V value Entry<K,V> parent Entry<K,V> left

 

Entry作为TreeMap内部的一个是有类，TreeMap类的root来对其引用

 

TreeMap 的具体实现如下，（省略了迭代）

package com.woxiaoe.collection.map;

import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import com.woxiaoe.collection.tree.STreeNode;
/**
 * TreeMap 的实现
 * @author 小e
 *
 * 2010-4-10 下午09:33:00
 */
public class TreeMap<K, V> implements Map<K, V> {
	private Entry<K, V> root;
	private int mapSize;
	private Set<K> keySet = null;
	public TreeMap() {
		root = null;
		mapSize = 0;
	}
	
	@Override
	public void clear() {
		// TODO Auto-generated method stub
		
	}

	@Override
	public boolean containsKey(Object key) {
		return getEntry((K) key) == null?false:true;
	}

	@Override
	public boolean containsValue(Object value) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public Set<java.util.Map.Entry<K, V>> entrySet() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public V get(Object key) {
		Entry<K, V> entry = getEntry((K) key);
		if(entry != null){
			return entry.getValue();
		}
		return null;
	}

	@Override
	public boolean isEmpty() {
		return mapSize != 0;
	}

	@Override
	public Set<K> keySet() {
		if(keySet == null){
			keySet = new Set<K>() {

				@Override
				public boolean add(K e) {
					throw new UnsupportedOperationException("不支持该操作");
				}

				@Override
				public boolean addAll(Collection<? extends K> c) {
					throw new UnsupportedOperationException("不支持该操作");
				}

				@Override
				public void clear() {
					// TODO Auto-generated method stub
					
				}

				@Override
				public boolean contains(Object o) {
					
					return TreeMap.this.containsKey(o);
				}

				@Override
				public boolean containsAll(Collection<?> c) {
					for (Iterator iterator = c.iterator(); iterator.hasNext();) {
						K key = (K) iterator.next();
						if(TreeMap.this.containsKey(key)){
							return true;
						}
					}
					return false;
				}

				@Override
				public boolean isEmpty() {
					return TreeMap.this.size() != 0;
				}

				@Override
				public Iterator<K> iterator() {
					return null;
				}

				@Override
				public boolean remove(Object o) {
					throw new UnsupportedOperationException("不支持该操作");
				}

				@Override
				public boolean removeAll(Collection<?> c) {
					throw new UnsupportedOperationException("不支持该操作");
				}

				@Override
				public boolean retainAll(Collection<?> c) {
					// TODO Auto-generated method stub
					return false;
				}

				@Override
				public int size() {
					return TreeMap.this.size();
				}

				@Override
				public Object[] toArray() {
					// TODO Auto-generated method stub
					return null;
				}

				@Override
				public <T> T[] toArray(T[] a) {
					// TODO Auto-generated method stub
					return null;
				}
			};
		}
		return null;
	}

	@Override
	public V put(K key, V value) {
		Entry<K, V> entry = root,parent = null,newNode;
		int result = 0;
		while(entry != null){
			parent = entry;
			result = ((Comparable<K>)entry.getKey()).compareTo(key);
			if(result == 0){//更新
				entry.setValue(value);
				return value;
			}else if(result > 0){
				entry = entry.getLeft();
			}else{
				entry = entry.getRight();
			}
		}
		
		newNode = new Entry<K, V>(key, value, parent);
		if(parent == null){//根结点的情况
			root = newNode;
		}else if(result > 0){
			parent.setLeft(newNode);
		}else{
			parent.setRight(newNode);
		}
		mapSize ++;
		return value;
	}

	@Override
	public void putAll(Map<? extends K, ? extends V> m) {
		// TODO Auto-generated method stub
		
	}

	@Override
	public V remove(Object key) {
		Entry<K, V> entry = getEntry((K) key);
		return remove(entry);
	}

	@Override
	public int size() {
		return mapSize;
	}

	@Override
	public Collection<V> values() {
		// TODO Auto-generated method stub
		return null;
	}
	/**
	 * 根据键的道一个Entry
	 * @param key
	 * @return
	 */
	private Entry<K, V> getEntry(K key){
		Entry<K, V> entry = root,returnEntry;
		int result = 0;
		while(entry != null){
			result = ((Comparable<K>)entry.getKey()).compareTo(key);
			if(result == 0){
				return entry;
			}else if(result > 0){
				entry = entry.getLeft();
			}else{
				entry = entry.getRight();
			}
		}
		
		return null;
		
	}
	/**
	 * 删除键值为key的键值对
	 * @param key
	 * @return
	 */
	private boolean removeEntry(K key){
		Entry<K, V> pEntry ,rEntry,entry = getEntry(key);//node的父节点，和node的子节点
		if(entry == null){
			return false;
		}
		/**
		 * 情况一，当节点至少有一棵空子树
		 */
		if(entry.getLeft() == null || entry.getRight() == null){
			pEntry = entry.getParent();
			
			if(entry.getLeft() == null){
				rEntry = entry.getRight();
			}else{
				rEntry = entry.getLeft();
			}
			
			if(rEntry != null){
				rEntry.setParent(pEntry);//将r的父节点指向p
			}
			
			if(pEntry == null){//node为root节点
				root = rEntry;
			}else if(((Comparable<K>)pEntry.getValue()).compareTo(entry.getKey()) < 0){
				pEntry.setRight(entry);
			}else{
				pEntry.setLeft(entry);
			}
		}else{
			rEntry = entry.getRight();
			pEntry = entry;
			
			/**
			 * 找到node的右子树中最大于node的最小值
			 */
			while(rEntry.getLeft() != null){
				pEntry = rEntry;
				rEntry = rEntry.getLeft();
			}
			/**
			 * 交换值
			 */
			entry.setValue(rEntry.getValue());
			
			if(pEntry == entry){//node 的下一结点 没有节点
				entry.setRight(rEntry.getRight());//
			}else{
				pEntry.setLeft(rEntry.getRight());
			}
			/**
			 * 将rNode的右子树 的 parent 接到pNode下
			 */
			if(rEntry.getRight() != null){
				rEntry.getRight().setParent(pEntry);
			}
		}
		return false;
	}
	private static class Entry<K,V> implements Map.Entry<K, V>{
		private K key;
		private V value;
		private Entry<K,V> left,right,parent;
		
		public Entry(K key,V value,Entry<K, V> parent) {
			this.key = key;
			this.value = value;
			this.parent = parent;
		}
		
		@Override
		public K getKey() {
			return this.key;
		}

		@Override
		public V getValue() {
			// TODO Auto-generated method stub
			return this.value;
		}

		@Override
		public V setValue(V value) {
			// TODO Auto-generated method stub
			return this.value = value;
		}

		public Entry<K, V> getLeft() {
			return left;
		}

		public void setLeft(Entry<K, V> left) {
			this.left = left;
		}

		public Entry<K, V> getRight() {
			return right;
		}

		public void setRight(Entry<K, V> right) {
			this.right = right;
		}

		public Entry<K, V> getParent() {
			return parent;
		}

		public void setParent(Entry<K, V> parent) {
			this.parent = parent;
		}
		
		
		
	}

}

 

测试类
package com.woxiaoe.collection.map;

import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.UUID;

import junit.framework.TestCase;

public class TestTreeMap extends TestCase {
	Map<Integer,String> map = new TreeMap<Integer, String>();
	int key = 0;
	@Override
	protected void setUp() throws Exception {
		Random r = new Random();
		String uuid = "";
		
		for(int i = 0; i < 100; i++){
			uuid = UUID.randomUUID().toString();
			key = r.nextInt(100);
			map.put(key,uuid);
			System.out.println("i:" + key + "\t uuid:" + uuid);
		}
		
	}
	public void testTreeMap(){
		System.out.println(map.size());
		System.out.println(map.get(key));
	}
}
 

Output：

 

i:35 uuid:5af915cd-f2ef-4668-8943-e61a8f4a0cb1

i:61 uuid:d9a71475-5762-4042-aa71-0f2683b9f660

i:21 uuid:2fd94a4c-4349-4771-9ed5-13bf002aae31

i:83 uuid:c3df4e3a-5220-4ba4-a9ee-4f956017c65a

i:88 uuid:187da75d-031d-4404-a60c-da7100f5b2da

i:97 uuid:0d0539ff-4b28-4b4f-8dc1-380f47eff8a5

i:37 uuid:81ca72d1-5f36-4dbc-99c6-fab3663e094f

i:63 uuid:25dd2755-c1cf-4a24-a7df-5e41eb14a135

i:45 uuid:f4a9e3be-39d4-4d26-be46-cab1e4aa1fb3

i:36 uuid:da148390-cbf6-4c42-a838-7fdd6ba807a1

i:30 uuid:4defb70f-9f65-4b9f-bf6f-1899331949f5

i:83 uuid:ea68fd7a-4c0d-458a-bfcd-81670f4c241c

i:3 uuid:4f0ff3a3-fd85-4209-a70c-076151a148ab

i:96 uuid:079af274-55cc-4c99-8869-323d7f779934

i:84 uuid:ec3d66dc-4e4c-4feb-acbc-4391d888e7d0

i:61 uuid:708cbe70-1f4e-484f-b9f0-eda41d31a707

i:95 uuid:b46cbac3-fb5c-4585-94e7-7b7c4abff5a7

i:42 uuid:142f023f-f2d8-4bf8-a03f-037eeabb5525

i:92 uuid:002280b6-38aa-4d3d-862d-ab471fab6c08

i:2 uuid:01667bc2-5b00-4a00-8290-9b1170910d96

i:56 uuid:7e8e2c04-1e9d-4167-910f-17176268836a

i:92 uuid:2bd08afb-3393-463b-8bfa-fe534618ff0b

i:46 uuid:81e644a2-0860-46a8-92f2-27bb24ab49fa

i:54 uuid:4ef7ef0d-cc79-4b6d-9bc0-1002093cd11a

i:42 uuid:68b3d575-eba8-427e-85c5-d936bc706733

i:23 uuid:ffe53eee-27c9-4682-ad3b-ab701517fdf1

i:19 uuid:aeacdb2e-6c35-4ac9-b018-28bda7bcd331

i:71 uuid:b40dbc71-57b7-4a25-8326-48e8edf117ee

i:8 uuid:b66d7d6d-8ba9-4b6b-9d4a-ae83c7cbcedc

i:34 uuid:41acf8cd-3c4b-4648-be82-112768cf0534

i:45 uuid:3d4e2c9c-623f-4a36-9e5c-289ecaf331bb

i:84 uuid:108f025e-ac1e-42ef-8e5d-2eb30d84d055

i:87 uuid:e7807eba-eb28-4e9d-a0aa-096dd630b41f

i:69 uuid:292c8e45-f98d-4b17-9c79-c1ca58554819

i:51 uuid:f69a94eb-31ad-4530-8104-af54fff712a7

i:61 uuid:06d68660-e5c0-4a28-8b31-92027e530d65

i:15 uuid:c1b1fbb6-5ba7-4383-af99-ec3a3ad35249

i:85 uuid:d68a7b8c-e401-4d7b-beb6-d269746b467a

i:84 uuid:24fd275e-bcd6-41ea-a062-7963ecccbffc

i:93 uuid:8cc88b89-14e3-411a-b3a2-9b1237ccf073

i:3 uuid:2b51c761-790c-4f2e-bb06-fea6b173edad

i:48 uuid:a4523cd5-896a-475f-98cc-762e4b5bc84d

i:91 uuid:d3dbf038-7045-42f1-8680-5d64b2d1218f

i:53 uuid:3a0ad304-a5ab-4e78-a35c-82734da03f9e

i:69 uuid:e9d22302-e28a-4814-8f1b-16b6606bb4bd

i:93 uuid:fc51a87b-8e9a-4a83-99e0-9245d8504038

i:45 uuid:00ad6c40-0831-453b-8fd8-028131f2fe6b

i:88 uuid:1f5d411e-f7e8-41cb-8c6a-005a26dacbd2

i:96 uuid:02ecd981-e4bd-4299-a7de-ced2c00bfc75

i:19 uuid:ce25c27c-7c90-448d-a0cd-08ed1728652e

i:44 uuid:7e3ce4ea-1483-48ef-95a0-1a44f50f5de4

i:49 uuid:76c9a712-104f-46d3-92dd-24a155e68632

i:62 uuid:afd8b6f0-9da6-418f-8a94-ffc02683ac26

i:43 uuid:487c19b2-2bce-4818-8827-e754fbd1c749

i:76 uuid:5a85fc2e-5bd5-48eb-b6d6-3b118d6da2ab

i:60 uuid:b024140b-5cff-4397-8306-fa9b06169812

i:87 uuid:74f2e878-2aed-4b1d-8932-fba5b2e7a401

i:46 uuid:0249b366-12e2-4c02-b220-db9525a15b63

i:32 uuid:d6fa08e4-6ff8-47c9-a35d-b0a7b02ff7f4

i:69 uuid:dc5d6ab0-4bae-4943-942f-8a88ae39a1c4

i:64 uuid:5b878280-ebba-404b-9b3d-7f68ae8908e7

i:60 uuid:d64da298-b2b9-456e-b0de-3b7d199d1ccc

i:67 uuid:6bc53a9a-fb5e-4c9d-bce4-5dacec428f1d

i:64 uuid:a7fab810-69b3-428d-a988-9fa31d173228

i:52 uuid:a806bf37-8d0f-422c-a93f-dc39a18f51b4

i:82 uuid:b9d21000-78c4-44a9-b324-2ae037146ab2

i:53 uuid:904b2e7d-7c27-469a-8ba6-841e42dff59a

i:58 uuid:372965d3-1e06-4bc6-b704-2e61759249dd

i:21 uuid:74f1ff1c-d1ca-4e2b-9c8b-347b55a82d13

i:17 uuid:e90294bb-b3fd-4536-b529-4d5985c67aca

i:97 uuid:90b522ba-1890-434c-9fa6-c60d3135d678

i:65 uuid:6dc42ff4-dec6-4e55-a71a-d308959602a9

i:59 uuid:215095ee-9a03-451f-be4c-621ced45a57d

i:23 uuid:2b080886-906b-407c-8ac4-7a163ab01934

i:45 uuid:35b73197-326d-4ebe-b1ce-3c00f83d86f8

i:89 uuid:b6b1680b-a0d4-4474-9613-441c26e38940

i:35 uuid:a8b7fe72-1c4a-4d63-888b-b1cd992bd7ed

i:97 uuid:49076b38-5f96-4bd5-be72-51e97d1da4e4

i:97 uuid:6e36536e-8172-4b9c-850a-f0b79478c992

i:27 uuid:31f7100b-8121-40af-ba4b-f470bb061c12

i:71 uuid:371f790b-e90d-47b6-b6fe-f58566aa2f24

i:4 uuid:66b880a5-53e5-4120-b48c-10f06833e233

i:33 uuid:7c3c223a-d49e-432c-85a8-0441b5574ac4

i:92 uuid:a27d5c94-8885-43c6-95b4-075f7033487d

i:14 uuid:aece1fb6-d821-40cb-9c35-17bac9a76b1c

i:83 uuid:ec831269-59c5-4234-99eb-513436fee57f

i:10 uuid:7dc45b5b-1a6b-4624-b95f-49856925080b

i:91 uuid:54faddab-037d-49fa-a112-09679cb621df

i:43 uuid:2618324a-2446-42c9-b828-71d93666456f

i:9 uuid:0ba9c5e4-00f0-4dcc-bd1a-74356e8c5828

i:40 uuid:ffe569b1-cf20-4103-9b80-da1b3b291e13

i:77 uuid:76807d50-3dc5-4603-9873-8a76e5823ad9

i:62 uuid:c0b48db7-eeb8-4c9f-82c7-be5d6448b4c4

i:59 uuid:e0a4df35-15ed-487f-b4b6-2be507c4b977

i:98 uuid:97563089-2577-4021-996e-3bfd7cc029af

i:86 uuid:ae8b79c1-c477-45f2-9b76-8c8bb5e13127

i:11 uuid:f783bc6e-ba17-41bb-9556-1f308b217397

i:24 uuid:077546ac-cafb-4618-8cb1-0dcdfde09df6

i:42 uuid:563ec38c-44c4-4b79-83c5-14b28a1d03b8

i:81 uuid:9de22af0-b78f-43d3-a52f-301c25f4588e

null

64

9de22af0-b78f-43d3-a52f-301c25f4588e


 载自：http://ideasforjava.iteye.com/blog/640931

分享到：
| Java乱码问题分析（转）
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    java jdk实列宝典 光盘源代码

    java为数据结构中的映射定义一个接口java.util.Map，有四个实现类HashMap Hashtable LinkedHashMap TreeMap用法和区别；对Map排序； 5字符串 使用String；判断一个字符串是否是合法的java标识符；使用StringBuffer；...

    Java 基础核心总结 +经典算法大全.rar

    示例:简易的客户端服务器通信 集合 集合框架总览 -、Iterator Iterable ListIterator 二、Map 和 Collection 接口Map 集合体系详解 HashMap LinkedHashMap TreeMap WeakHashMap Hashtable Collection 集合体系详解 ...

    疯狂JAVA讲义

    7.6.2 SortedMap接口和TreeMap实现类 276 7.6.3 WeakHashMap实现类 279 7.6.4 IdentityHashMap实现类 280 7.6.5 EnumMap实现类 281 7.7 HashSet和HashMap的性能选项 282 7.8 操作集合的工具类：Collections 283...

    DataStructureJava:主要数据结构——java中的简单实现

    数据结构Java 主要数据结构——java中的简单实现如何使用集合：-&gt; JDK（Java集合）-&gt; Guava（谷歌）-&gt; Commons-collections（Apache） 主要抽象数据结构——ADS列表（ArrayList、LinkedList、Vector）栈（FIFO）队列...

    Voronoi-Treemap-Library:Java库，用于计算Voronoi树图

    Arlind Nocaj，Ulrik Brandes，“计算Voronoi树图：更快，更简单，且与分辨率无关”，计算机图形学论坛，第一卷，第1期。 31号3，2012年6月，第855-864页 请注意，本文使用的实现是另一种实现，但是运行时应为大约...

    Java常见面试题208道.docx

    面试题包括以下十九部分：Java 基础、容器、多线程、反射、对象拷贝、Java Web 模块、异常、网络、设计模式、Spring/Spring MVC、Spring Boot/Spring Cloud、Hibernate、Mybatis、RabbitMQ、Kafka、Zookeeper、MySql...

    Java JDK实例宝典

    第1章 Java基础 1.1 转换基本数据类型 1.2 Java的运算符 1.3 控制程序的流程 1.4 计算阶乘 1.5 实现命令行程序 第2章 Java面向对象程序设计 2. 1 复数类 2. 2 equals.chashCode...

    数据结构与算法分析Java语言描述(第二版)

    Java51.4.1 使用Object表示泛型1.4.2 基本类型的包装1.4.3 使用接口类型表示泛型1.4.4 数组类型的兼容性1.5 利用Java5泛性实现泛型特性成分1.5.1 简单的泛型类和接口1.5.2 自动装箱/拆箱1.5.3 带有限制的通配符...

    trie:Trie数据结构的Java实现

    Prefix Trie数据结构的Java实现。 介绍 尝试是类似于基于有序树的数据结构的地图，可快速搜索O(k)的顺序，其中k是键的长度。 阅读有关trie的更多信息。 动机 它最初是为在我的Android应用程序T9 App Launcher中使用...

    数据结构与算法分析_Java语言描述(第2版)]

    表、栈和队列3.1 抽象数据类型3.2 表ADT3.2.1 表的简单数组实现3.2.2 简单链表3.3 JavaCollectionsAPI中的表3.3.1 Collection接口3.3.2 Iterator接口3.3.3 List接口、ArrayList类和LinkedList类3.3.4 例：remove...

    史上最全java面试，103项重点知识，带目录

    22. 如何决定使用 HashMap 还是 TreeMap？ 10 23. 说一下 HashMap 的实现原理？ 10 24. 说一下 HashSet 的实现原理？ 11 25. ArrayList 和 LinkedList 的区别是什么？ 11 26. 如何实现数组和 List 之间的转换？ 11 ...

    数据结构与算法分析 Java语言描述第2版

    表、栈和队列3.1 抽象数据类型3.2 表ADT3.2.1 表的简单数组实现3.2.2 简单链表3.3 JavaCollectionsAPI中的表3.3.1 Collection接口3.3.2 Iterator接口3.3.3 List接口、ArrayList类和LinkedList类3.3.4 例：remove...

    数据结构与算法分析_Java语言描述(第2版)

    4.8.3 TreeSet类和TreeMap类的实现 4.8.4 使用多个映射的例 小结 练习 参考文献 第5章 散列 5.1 一般想法 5.2 散列函数 5.3 分离链接法 5.4 不用链表的散列表 5.4.1 线性探测法 5.4.2 平方探测法 5.4.3 双散列 5.5 ...

    数据结构与算法分析-Java语言描述(第2版)_2_2

    4.5.1　一个简单的想法（不能直接使用）　4.5.2　展开　4.6　树的遍历　4.7　b树　4.8　标准库中的集合与映射　4.8.1　关于set接口　4.8.2　关于map接口　4.8.3　treeset类和treemap类的实现　4.8.4　使用多个映射...

    数据结构与算法分析-Java语言描述(第2版)_1_2

    4.5.1　一个简单的想法（不能直接使用）　4.5.2　展开　4.6　树的遍历　4.7　b树　4.8　标准库中的集合与映射　4.8.1　关于set接口　4.8.2　关于map接口　4.8.3　treeset类和treemap类的实现　4.8.4　使用多个映射...

    涵盖了90%以上的面试题

    Java中的异常处理机制的简单原理和应用。 java socket java序列化 JVM加载class文件的原理 双亲委派模型 为什么要自定义类加载器 如何自定义类加载器 什么是GC 内存泄漏和内存溢出 Java的内存模型(JVM的内存划分) ...

    21天学通Java-由浅入深

    第一篇 基础篇 第1章 Java简介（精彩视频：33分钟） 21 1.1 Java的平台简介 21 1.2 安装工具包 22 1.2.1 下载JDK 22 1.2.2 安装JDK 24 1.2.3 查看与设置环境变量 25 1.2.4 JDK常用命令 27 1.2.5 Java各个目录含义 28...

    Java开发技术大全 电子版

    1.3一个简单的Java应用程序14 1.4一个简单的Java小程序16 1.5本章小结18 第2章Java语言基础19 2.1Java语言的特点19 2.2Java程序的构成21 2.3数据类 型23 2.3.1基本数据类型23 2.3.2常量25 2.3.3变量26 ...

Magicbox
Global site tag (gtag.js) - Google Analytics