`
hz_chenwenbiao
  • 浏览: 1006422 次
  • 性别: 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乱码问题分析（转）
评论
发表评论

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

相关推荐

    TreeMap源码

    TreeMap是Java集合框架中的一种有序映射数据结构，它实现了SortedMap接口，提供了按自然顺序或自定义比较器顺序存储键值对的能力。在深入理解TreeMap的源码之前，我们首先要了解其背后的基石——红黑树。 红黑树...

    Java TreeMap排序算法实例

    在Java中，TreeMap排序算法的实现可以通过两种方式：一是使用TreeMap的自然排序，二是使用Comparator接口来实现自定义的排序规则。自然排序是指根据键值对的自然顺序进行排序，而Comparator接口则可以根据特定的排序...

    java 中 TreeMap排序

    在Java编程语言中，`TreeMap`是一种基于红黑树数据结构实现的键值对容器，与`HashMap`不同，`TreeMap`自动按照键的自然顺序或者自定义的比较器进行排序。当我们需要存储的数据有特定的排序需求时，`TreeMap`便成为一...

    Map，HashMap,TreeMap的使用

    在 Java 中，HashMap、LinkedHashMap、TreeMap 都实现了 Map 接口，都是 Map 的子类，每个子类都有其特点和使用场景。 HashMap HashMap 是最常用的 Map 实现类，它根据键的哈希码值存储数据，能够快速地存储和获取...

    Java二维数组实现简单Map

    尽管Java提供了内置的Map接口（如HashMap、TreeMap等），但有时为了学习或特定需求，我们可能会用基本类型的数据结构来实现Map。这篇博客文章（链接已省略）可能介绍了如何通过二维数组实现这个概念。 首先，我们...

    红黑树Java实现

    - Java集合框架：`TreeMap`和`TreeSet`是基于红黑树实现的，提供有序的元素存储和高效的查找、插入和删除操作。 - 数据库索引：数据库系统如MySQL的InnoDB存储引擎使用红黑树作为索引结构。 - C++标准模板库(STL)...

    java-数据结构代码实现

    Java中的`TreeMap`和`TreeSet`基于红黑树实现，你可以在代码中找到关于树操作的实现。 7. **图**：图数据结构用于表示对象之间的复杂关系，如邻接矩阵和邻接表是常见的图表示方式。在实际项目中，图可能用于网络...

    文本数据库数据库操纵JAVA实现版本

    - 使用Java设计并实现了一个简单的文本数据库系统。 - 数据的存储和检索通过Hashtable或类似数据结构（如TreeMap）实现，以键值对形式存储数据。 - 应用程序支持多线程环境，可能采用了线程安全的数据结构或同步机制...

    Java中HashMap和TreeMap的区别深入理解

    HashMap和TreeMap是Java中两种常用的Map实现，它们各自具有不同的特性和使用场景。 HashMap是基于哈希表实现的，其核心思想是通过键对象的hashCode()方法来快速定位到对应的桶（bucket），从而提高查找效率。...

    红黑树的插入-java实现

    在Java中，红黑树被广泛应用于`java.util.TreeMap`和`java.util.TreeSet`等数据结构中。 红黑树的核心特性有五条： 1. 每个节点不是红色就是黑色。 2. 根节点是黑色。 3. 所有叶子节点（NIL或空节点）是黑色。 4. ...

    在Java中如何决定使用 HashMap 还是 TreeMap

    在 Java 中，HashMap 和 TreeMap 都是常用的 Map 实现类，但是在实际开发中，选择哪种 Map 实现类往往让人感到迷茫。下面我们将详细介绍 HashMap 和 TreeMap 的特点、优缺点和使用场景，帮助您更好地选择合适的 Map ...

    Java实现的红黑树

    - 集合框架：Java的`TreeMap`和`TreeSet`利用红黑树实现有序映射和有序集合。 - 其他：内存分配器、编译器符号表等。 总的来说，红黑树是一种重要的数据结构，它的平衡策略使其在各种场景下表现出高效性。通过...

    java简单学生管理系统

    Java简单学生管理系统是一种基于Java编程语言开发的课程设计项目，主要目标是实现对学生信息的管理功能，包括添加、删除和修改等基本操作。这个系统通常适用于教学环境，帮助初学者理解面向对象编程、数据结构以及...

    红黑树的Java实现参考源码

    在Java实现中，红黑树的核心类是`java.util.TreeMap.Node`，这个类代表树中的一个节点，包含键值对以及颜色属性。插入操作会遵循以下步骤： 1. 首先，新插入的节点默认为红色，因为红色节点不会破坏红黑树的性质。 ...

    JAVA实现的红黑树

    在Java中，红黑树被广泛应用于集合框架中的`java.util.TreeMap`和`java.util.TreeSet`等类。 1. **红黑树的性质** - 每个节点要么是红色要么是黑色。 - 根节点是黑色。 - 所有叶子节点（NIL或空节点）都是黑色。...

    通过分析_JDK_源代码研究_TreeMap_红黑树算法实现.docx

    TreeMap 和 TreeSet 是 Java 集合框架中的重要成员，它们提供了基于红黑树的数据结构实现。从给定部分源代码可以看到，TreeSet 的构造器实际上依赖于 TreeMap 的实例化。具体来说： 1. **构造器分析**： - TreeSet...

    java 红黑树实现.rar

    在Java中，红黑树被广泛应用于`java.util.TreeMap`、`java.util.TreeSet`以及`java.util.HashMap`的内部实现。 红黑树的特性： 1. 每个节点要么是红色，要么是黑色。 2. 根节点是黑色。 3. 所有叶子节点（NIL或空...

    Java编写简单系统

    Java编程语言是软件开发领域广泛使用的工具，尤其适合构建各种类型的应用系统，包括简单的系统。在本主题中，我们将深入探讨如何使用Java来编写一个简单的系统。首先，我们需要理解Java的基础，包括语法、类与对象、...

    Java学习.pdf

    Java是一种广泛使用的高级编程语言，它是一种面向对象的编程语言，具有跨平台性、简单性、安全性、可移植性、解释执行和高性能等特性。Java在企业级应用、移动应用、大数据处理、Web应用开发等方面都有广泛的应用。 ...

    Java实现字典功能xxxxxx

    在Java编程语言中，实现字典...总之，实现Java字典功能涉及选择合适的数据结构（如`HashMap`或`TreeMap`）、应用有效的搜索算法，以及可能的GUI设计。通过熟练掌握这些知识点，开发者可以构建出高效、易用的字典应用。

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