锐客网

  1. 首页 > 生活百科 > it技术 > >

红黑树代码实现java java 红黑树与b树区别

IT技术元素

java集合类哪个函数可以java集合里面的函数
java集合里面的函数_java集合【1】——— 从集合接口框架说起
百里方欣
原创
关注
0点赞·155人阅读
(一) java集合分类
之前大概分为三种 ， Set，List，Map三种，JDK5之后 ， 增加Queue.主要由Collection和Map两个接口衍生出来,同时Collection接口继承Iterable接口，所以我们也可以说java里面的集合类主要是由Iterable和Map两个接口以及他们的子接口或者其实现类组成 。我们可以认为Collection接口定义了单列集合的规范，每次只能存储一个元素 ， 而Map接口定义了双列集合的规范 ， 每次能存储一对元素 。
Iterable接口:主要是实现遍历功能
Collection接口: 允许重复
Set接口：无序，元素不可重复,访问元素只能通过元素本身来访问 。
List接口：有序且可重复，可以根据元素的索引来访问集合中的元素 。
Queue接口：队列集合
Map接口：映射关系，简单理解为键值对，Key不可重复，与Collection接口关系不大，只是个别函数使用到 。
整个接口框架关系如下(来自百度百科)：
(1) Iterable接口
1. 内部定义的方法
java集合最源头的接口，实现这个接口的作用主要是集合对象可以通过迭代器去遍历每一个元素 。
源码如下：
// 返回一个内部元素为T类型的迭代器(JDK1.5只有这个接口)
Iterator iterator();
// 遍历内部元素 ， action意思为动作 ， 指可以对每个元素进行操作(JDK1.8添加)
default void forEach(Consumer super T action) {}
// 创建并返回一个可分割迭代器(JDK1.8添加) ， 分割的迭代器主要是提供可以并行遍历元素的迭代器，可以适应现在cpu多核的能力，加快速度 。
default Spliterator spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
从上面可以看出，foreach迭代以及可分割迭代，都加了default关键字 ， 这个是Java 8 新的关键字，以前接口的所有接口，具体子类都必须实现 ， 而对于deafult关键字标识的方法，其子类可以不用实现，这也是接口规范发生变化的一点 。
【红黑树代码实现java java 红黑树与b树区别】下面我们分别展示三个接口的调用：
1.1 iterator方法
public static void iteratorHasNext(){
List list=new ArrayList();
list.add("Jam");
list.add("Jane");
list.add("Sam");
// 返回迭代器
Iterator iterator=list.iterator();
// hashNext可以判断是否还有元素
while(iterator.hasNext()){
//next()作用是返回当前指针指向的元素,之后将指针移向下个元素
System.out.println(iterator.next());
}
}
当然也可以使用for-each loop方式遍历
for (String item : list) {
System.out.println(item);
}
但是实际上，这种写法在class文件中也是会转成迭代器形式，这只是一个语法糖 。class文件如下：
public class IterableTest {
public IterableTest() { }
public static void main(String[] args) {
iteratorHasNext();
}
public static void iteratorHasNext() {
List list = new ArrayList();
list.add("Jam");
list.add("Jane");
list.add("Sam");
Iterator iterator = list.iterator();
Iterator var2 = list.iterator();
while(var2.hasNext()) {
String item = (String)var2.next();
System.out.println(item);
}
}
}
需要注意的一点是，迭代遍历的时候 ， 如果删除或者添加元素 ， 都会抛出修改异常，这是由于快速失败【fast-fail】机制 。
public static void iteratorHasNext(){
List list=new ArrayList();
list.add("Jam");
list.add("Jane");
list.add("Sam");
for (String item : list) {
if(item.equals("Jam")){
list.remove(item);
}
System.out.println(item);
}
}
从下面的错误我们可以看出，第一个元素是有被打印出来的，也就是remove操作是成功的，只是遍历到第二个元素的时候，迭代器检查，发现被改变了，所以抛出了异常 。
Jam
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
at IterableTest.iteratorHasNext(IterableTest.java:15)
at IterableTest.main(IterableTest.java:7)
1.2 forEach方法
其实就是把对每一个元素的操作当成了一个对象传递进来，对每一个元素进行处理 。
default void forEach(Consumer super T action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
```java
当然像ArrayList自然也是有自己的实现的，那我们就可以使用这样的写法,简洁优雅 。forEach方法在java8中参数是`java.util.function.Consumer`,可以称为**消费行为**或者说**动作**类型 。
```java
list.forEach(x - System.out.print(x));
同时 ， 我们只要实现Consumer接口，就可以自定义动作，如果不自定义，默认迭代顺序是按照元素的顺序 。
public class ConsumerTest {
public static void main(String[] args) {
List list=new ArrayList();
list.add("Jam");
list.add("Jane");
list.add("Sam");
MyConsumer myConsumer = new MyConsumer();
Iterator it = list.iterator();
list.forEach(myConsumer);
}
static class MyConsumer implements Consumer {
@Override
public void accept(Object t) {
System.out.println("自定义打?。?t);
}
}
}
输出的结果：
自定义打?。篔am
自定义打?。篔ane
自定义打?。篠am
1.3 spliterator方法
这是一个为了并行遍历数据元素而设计的迭代方法，返回的是Spliterator，是专门并行遍历的迭代器 。以发挥多核时代的处理器性能，java默认在集合框架中提供了一个默认的Spliterator实现，底层也就是Stream.isParallel()实现的，我们可以看一下源码：
// stream使用的就是spliterator
default Stream stream() {
return StreamSupport.stream(spliterator(), false);
}
default Spliterator spliterator() {
return Spliterators.spliterator(this, 0);
}
public static Stream stream(Spliterator spliterator, boolean parallel) {
Objects.requireNonNull(spliterator);
return new ReferencePipeline.Head(spliterator,
StreamOpFlag.fromCharacteristics(spliterator),
parallel);
}
使用的方法如下：
public static void spliterator(){
List list = Arrays.asList("1", "2", "3","4","5","6","7","8","9","10");
// 获取可迭代器
Spliterator spliterator = list.spliterator();
// 一个一个遍历
System.out.println("tryAdvance: ");
spliterator.tryAdvance(item-System.out.print(item " "));
spliterator.tryAdvance(item-System.out.print(item " "));
System.out.println("\n-------------------------------------------");
// 依次遍历剩下的
System.out.println("forEachRemaining: ");
spliterator.forEachRemaining(item-System.out.print(item " "));
System.out.println("\n------------------------------------------");
// spliterator1:0~10
Spliterator spliterator1 = list.spliterator();
// spliterator1:6~10 spliterator2:0~5
Spliterator spliterator2 = spliterator1.trySplit();
// spliterator1:8~10 spliterator3:6~7
Spliterator spliterator3 = spliterator1.trySplit();
System.out.println("spliterator1: ");
spliterator1.forEachRemaining(item-System.out.print(item " "));
System.out.println("\n------------------------------------------");
System.out.println("spliterator2: ");
spliterator2.forEachRemaining(item-System.out.print(item " "));
System.out.println("\n------------------------------------------");
System.out.println("spliterator3: ");
spliterator3.forEachRemaining(item-System.out.print(item " "));
}
tryAdvance() 一个一个元素进行遍历
forEachRemaining() 顺序地分块遍历
trySplit()进行分区形成另外的 Spliterator，使用在并行操作中，分出来的是前面一半，就是不断把前面一部分分出来
结果如下：
tryAdvance:
1 2
-------------------------------------------
forEachRemaining:
3 4 5 6 7 8 9 10
------------------------------------------
spliterator1:
8 9 10
------------------------------------------
spliterator2:
1 2 3 4 5
------------------------------------------
spliterator3:
6 7
还有一些其他的用法在这里就不列举了，主要是trySplit()之后，可以用于多线程遍历 。理想的时候，可以平均分成两半，有利于并行计算 ， 但是不是一定平分的 。
2. Collection接口 extend Iterable
Collection接口可以算是集合类的一个根接口之一 ， 一般不能够直接使用，只是定义了一个规范，定义了添加 ， 删除等管理数据的方法 。继承Collection接口的有List ， Set,Queue,不过Queue定义了自己的一些接口，相对来说和其他的差异比较大 。
2.1 内部定义的方法
源码如下：
boolean add(Object o) //添加元素
boolean remove(Object o) //移除元素
boolean addAll(Collection c) //批量添加
boolean removeAll(Collection c) //批量移除
void retainAll(Collection c) // 移除在c中不存在的元素
void clear() //清空集合
int size() //集合大小
boolean isEmpty() //是否为空
boolean contains(Object o) //是否包含在集合中
boolean containsAll(Collection c) //是否包含所有的元素
Iterator iterator() // 获取迭代器
Object[] toArray() // 转成数组
default boolean removeIf(Predicate super E filter) {} // 删除集合中复合条件的元素 ， 删除成功返回true
boolean equals(Object o)
int hashCode()
default Spliterator spliterator() {} //获取可分割迭代器
default Stream stream() {} //获取流
default Stream parallelStream() {} //获取并行流
里面获取并行流的方法parallelStream(),其实就是通过默认的ForkJoinPool(主要用来使用分治法(Divide-and-Conquer Algorithm)来解决问题)，提高多线程任务的速度 。我们可以使用ArrayList来演示一下平行处理能力 。例如下面的例子，输出的顺序就不一定是1,2,3... ， 可能是乱序的，这是因为任务会被分成多个小任务，任务执行是没有特定的顺序的 。
List list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
list.parallelStream()
.forEach(out::println);
2.2 继承Collection的主要接口
graph LR;
Collection --List-有顺序,可重复
List-有顺序,可重复 --LinkedList-使用链表实现,线程不安全
List-有顺序,可重复 --ArrayList-数组实现,线程不安全
List-有顺序,可重复 --Vector-数组实现,线程安全
Vector-数组实现,线程安全 --Stack-堆栈,先进后出
Collection--Set-不可重复,内部排序
Set-不可重复,内部排序--HashSet-hash表存储
HashSet-hash表存储--LinkHashSet-链表维护插入顺序
Set-不可重复,内部排序--TreeSet-二叉树实现,排序
Collection--Queue-队列,先进先出
2.2.1 List extend Collection
继承于Collection接口，有顺序，取出的顺序与存入的顺序一致，有索引，可以根据索引获取数据，允许存储重复的元素，可以放入为null的元素 。
最常见的三个实现类就是ArrayList ， Vector,LinkedList，ArrayList和Vector都是内部封装了对数组的操作，唯一不同的是，Vector是线程安全的，而ArrayList不是，理论上ArrayList操作的效率会比Vector好一些 。
里面是接口定义的方法：
int size(); //获取大小
boolean isEmpty(); //判断是否为空
boolean contains(Object o); //是否包含某个元素
Iterator iterator(); //获取迭代器
Object[] toArray(); // 转化成为数组(对象)
T[] toArray(T[] a); // 转化为数组(特定位某个类)
boolean add(E e); //添加
boolean remove(Object o); //移除元素
boolean containsAll(Collection c); // 是否包含所有的元素
boolean addAll(Collection extends E c); //批量添加
boolean addAll(int index, Collection extends E c); //批量添加 ， 指定开始的索引
boolean removeAll(Collection c); //批量移除
boolean retainAll(Collection c); //将c中不包含的元素移除
default void replaceAll(UnaryOperator operator) {}//替换
default void sort(Comparator super E c) {}// 排序
void clear();//清除所有的元素
boolean equals(Object o);//是否相等
int hashCode(); //计算获取hash值
E get(int index); //通过索引获取元素
E set(int index, E element);//修改元素
void add(int index, E element);//在指定位置插入元素
E remove(int index);//根据索引移除某个元素
int indexOf(Object o); //根据对象获取索引
int lastIndexOf(Object o); //获取对象元素的最后一个元素
ListIterator listIterator(); // 获取List迭代器
ListIterator listIterator(int index); // 根据索引获取当前的位置的迭代器
List subList(int fromIndex, int toIndex); //截取某一段数据
default Spliterator spliterator(){} //获取可切分迭代器
上面的方法都比较简单，值得一提的是里面出现了ListIterator，这是一个功能更加强大的迭代器，继承于Iterator,只能用于List类型的访问，拓展功能例如：通过调用listIterator()方法获得一个指向List开头的ListIterator，也可以调用listIterator(n)获取一个指定索引为n的元素的ListIterator,这是一个可以双向移动的迭代器 。
操作数组索引的时候需要注意，由于List的实现类底层很多都是数组，所以索引越界会报错IndexOutOfBoundsException 。
说起List的实现子类：
ArrayList：底层存储结构是数组结构，增加删除比较慢，查找比较快 ， 是最常用的List集合 。线程不安全 。
LinkedList：底层是链表结构，增加删除比较快，但是查找比较慢 。线程不安全 。
Vector：和ArrayList差不多，但是是线程安全的，即同步 。
2.2.2 Set extend Collection
Set接口，不允许放入重复的元素，也就是如果相同 ， 则只存储其中一个 。
下面是源码方法：
int size(); //获取大小
boolean isEmpty(); //是否为空
boolean contains(Object o); //是否包含某个元素
Iterator iterator(); //获取迭代器
Object[] toArray(); //转化成为数组
T[] toArray(T[] a); //转化为特定类的数组
boolean add(E e); //添加元素
boolean remove(Object o); //移除元素
boolean containsAll(Collection c); //是否包含所有的元素
boolean addAll(Collection extends E c); //批量添加
boolean retainAll(Collection c); //移除所有不存在于c集合中的元素
boolean removeAll(Collection c); //移除所有在c集合中存在的元素
void clear(); //清空集合
boolean equals(Object o); //是否相等
int hashCode(); //计算hashcode
default Spliterator spliterator() {} //获取可分割迭代器
主要的子类：
HashSet
允许空值
通过HashCode方法计算获取hash值，确定存储位置，无序 。
LinkedHashSet
HashSet的子类
有顺序
TreeSet
如果无参数构建Set，则需要实现Comparable方法 。
亦可以创建时传入比较方法，用于排序 。
2.2.3 Queue extend Collection
队列接口，在Collection接口的接触上添加了增删改查接口定义，一般默认是先进先出，即FIFO，除了优先队列和栈，优先队列是自己定义了排序的优先顺序，队列中不允许放入null元素 。
下面是源码：
boolean add(E e); //插入一个元素到队列，失败时返回IllegalStateException (如果队列容量不够)
boolean offer(E e); //插入一个元素到队列，失败时返回false
E remove(); //移除队列头的元素并移除
E poll(); //返回并移除队列的头部元素，队列为空时返回null
E element(); //返回队列头元素
E peek(); //返回队列头部的元素，队列为空时返回null
主要的子接口以及实现类有：
Deque(接口):Queue的子接口，双向队列，可以从两边存取
ArrayDeque：Deque的实现类 ， 底层用数组实现，数据存贮在数组中
AbstractQueue：Queue的子接口，仅实现了add、remove和element三个方法
PriorityQueue：按照默认或者自己定义的顺序来排序元素，底层使用堆(完全二叉树)实现，使用动态数组实现，
BlockingQueue： 在java.util.concurrent包中，阻塞队列，满足当前无法处理的操作 。
(2) Map接口
定义双列集合的规范Map，每次存储一对元素 ， 即key和value 。
key的类型可以和value的类型相同，也可以不同，任意的引用类型都可以 。
key是不允许重复的，但是value是可以重复的，所谓重复是指计算的hash值系统 。
下面的源码的方法：
V put(K key, V value); // 添加元素
V remove(Object key); // 删除元素
void putAll(Map extends K, ? extends V m); // 批量添加
void clear() // 移除所有元素
V get(Object key); // 通过key查询元素
int size(); // 查询集合大小
boolean isEmpty(); // 集合是否为空
boolean containsKey(Object key); // 是否包含某个key
boolean containsValue(Object value); // 是否包含某个value
Set keySet(); // 获取所有key的set集合
Collection values(); // 获取所有的value的set集合
Set entrySet(); // 返回键值对的set ， 每一个键值对是一个entry对象
boolean equals(Object o); // 用于比较的函数
int hashCode(); // 计算hashcode
default V getOrDefault(Object key, V defaultValue) // 获取key对应的Value，没有则返回默认值()
default void forEach(BiConsumer super K, ? super V action) {} // 遍历
default void replaceAll(BiFunction super K, ? super V, ? extends V function) {} // 批量替换
// 缺少这个key的时候才会添加进去
// 返回值是是key对应的value值，如果不存在，则返回的是刚刚放进去的value
default V putIfAbsent(K key, V value) {}
default boolean remove(Object key, Object value) {} // 移除元素
default boolean replace(K key, V oldValue, V newValue) {} // 替换
default V replace(K key, V value) {} //替换
// 和putIfAbsent有点像，只不过传进去的mappingFunction是映射函数 ， 也就是如果不存在key对应的value，将会执行函数，函数返回值会被当成value添加进去，同时返回新的value值
default V computeIfAbsent(K key,Function super K, ? extends V mappingFunction) {}
// 和computeIfAbsent方法相反 ， 只有key存在的时候，才会执行函数，并且返回
default V computeIfPresent(K key,BiFunction super K, ? super V, ? extends V remappingFunction) {}
// 不管如何都会执行映射函数，返回value
default V compute(K key,BiFunction super K, ? super V, ? extends V remappingFunction) {}
default V merge(K key, V value,BiFunction super V, ? super V, ? extends V remappingFunction) {}
值得注意的是，Map里面定义了一个Entry类，其实就是定义了一个存储数据的类型，一个entry就是一个.
Map的常用的实现子类：
HashMap：由数组和链表组成，线程不安全 ， 无序 。
LinkedHashMap：如果我们需要是有序的，那么就需要它，时间和空间效率没有HashMap那么高，底层是维护一条双向链表，保证了插入的顺序 。
ConcurrentHashMap：线程安全，1.7JDK使用锁分离，每一段Segment都有自己的独立锁 ， 相对来说效率也比较高 。JDK1.8抛弃了Segment，使用Node数组 链表和红黑树实现，在线程安全控制上使用Synchronize和CAS ， 可以认为是优化的线程安全的HashMap 。
HashTable：对比与HashMap主要是使用关键字synchronize，加上同步锁，线程安全 。
(二)总结
这些集合原始接口到底是什么？为什么需要？
我想，这些接口其实都是一种规则/规范的定义 ， 如果不这么做也可以，所有的子类自己实现 ， 但是从迭代以及维护的角度来说，这就是一种抽象或者分类，比如定义了Iterator接口，某一些类就可以去继承或者实现 ， 那就得遵守这个规范/契约 。可以有所拓展，每个子类的拓展不一样 ， 所以每个类就各有所长，但是都有一个中心，就是原始的集合接口 。比如实现Map接口的所有类的中心思想都不变 ， 只是各有所长，各分千秋，形成了大千集合世界 。
【作者简介】：
秦怀，公众号【秦怀杂货店】作者 ， 技术之路不在一时，山高水长，纵使缓慢，驰而不息 。个人写作方向：Java源码解析，JDBC，Mybatis，Spring ， redis，分布式，剑指Offer，LeetCode等 ， 认真写好每一篇文章 ， 不喜欢标题党，不喜欢花里胡哨，大多写系列文章 ， 不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料 。遗漏或者错误之处，还望指正 。
平日时间宝贵 ， 只能使用晚上以及周末时间学习写作 ， 关注我 ， 我们一起成长吧~
Java中HashMap和TreeMap的区别深入理解首先介绍一下什么是Map 。在数组中我们是通过数组下标来对其内容索引的，而在Map中我们通过对象来对对象进行索引，用来索引的对象叫做key，其对应的对象叫做value 。这就是我们平时说的键值对 。
HashMap通过hashcode对其内容进行快速查找，而 TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的） 。
HashMap 非线程安全 TreeMap 非线程安全
线程安全
在Java里，线程安全一般体现在两个方面：
1、多个thread对同一个java实例的访问（read和modify）不会相互干扰 ， 它主要体现在关键字synchronized 。如ArrayList和Vector，HashMap和Hashtable
（后者每个方法前都有synchronized关键字） 。如果你在interator一个List对象时，其它线程remove一个element ， 问题就出现了 。
2、每个线程都有自己的字段，而不会在多个线程之间共享 。它主要体现在java.lang.ThreadLocal类，而没有Java关键字支持，如像static、transient那样 。
1.AbstractMap抽象类和SortedMap接口
AbstractMap抽象类：(HashMap继承AbstractMap)覆盖了equals()和hashCode()方法以确保两个相等映射返回相同的哈希码 。如果两个映射大小相等、包含同样的键且每个键在这两个映射中对应的值都相同，则这两个映射相等 。映射的哈希码是映射元素哈希码的总和，其中每个元素是Map.Entry接口的一个实现 。因此 ， 不论映射内部顺序如何，两个相等映射会报告相同的哈希码 。
SortedMap接口：（TreeMap继承自SortedMap）它用来保持键的有序顺序 。SortedMap接口为映像的视图(子集) ， 包括两个端点提供了访问方法 。除了排序是作用于映射的键以外，处理SortedMap和处理SortedSet一样 。添加到SortedMap实现类的元素必须实现Comparable接口 ， 否则您必须给它的构造函数提供一个Comparator接口的实现 。TreeMap类是它的唯一一份实现 。
2.两种常规Map实现
HashMap：基于哈希表实现 。使用HashMap要求添加的键类明确定义了hashCode()和equals()[可以重写hashCode()和equals()]，为了优化HashMap空间的使用，您可以调优初始容量和负载因子 。
(1)HashMap(): 构建一个空的哈希映像
(2)HashMap(Map m): 构建一个哈希映像 ， 并且添加映像m的所有映射
(3)HashMap(int initialCapacity): 构建一个拥有特定容量的空的哈希映像
(4)HashMap(int initialCapacity, float loadFactor): 构建一个拥有特定容量和加载因子的空的哈希映像
TreeMap：基于红黑树实现 。TreeMap没有调优选项，因为该树总处于平衡状态 。
(1)TreeMap():构建一个空的映像树
(2)TreeMap(Map m): 构建一个映像树，并且添加映像m中所有元素
(3)TreeMap(Comparator c): 构建一个映像树，并且使用特定的比较器对关键字进行排序
(4)TreeMap(SortedMap s): 构建一个映像树，添加映像树s中所有映射 ， 并且使用与有序映像s相同的比较器排序
3.两种常规Map性能
HashMap：适用于在Map中插入、删除和定位元素 。
Treemap：适用于按自然顺序或自定义顺序遍历键(key) 。
4.总结
HashMap通常比TreeMap快一点(树和哈希表的数据结构使然)，建议多使用HashMap，在需要排序的Map时候才用TreeMap 。
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
public class HashMaps {
public static void main(String[] args) {
MapString, String map = new HashMapString, String();
map.put("a", "aaa");
map.put("b", "bbb");
map.put("c", "ccc");
map.put("d", "ddd");
IteratorString iterator = map.keySet().iterator();
while (iterator.hasNext()) {
Object key = iterator.next();
System.out.println("map.get(key) is :"map.get(key));
}
// 定义HashTable,用来测试
HashtableString, String tab = new HashtableString, String();
tab.put("a", "aaa");
tab.put("b", "bbb");
tab.put("c", "ccc");
tab.put("d", "ddd");
IteratorString iterator_1 = tab.keySet().iterator();
while (iterator_1.hasNext()) {
Object key = iterator_1.next();
System.out.println("tab.get(key) is :"tab.get(key));
}
TreeMapString, String tmp = new TreeMapString, String();
tmp.put("a", "aaa");
tmp.put("b", "bbb");
tmp.put("c", "ccc");
tmp.put("d", "cdc");
IteratorString iterator_2 = tmp.keySet().iterator();
while (iterator_2.hasNext()) {
Object key = iterator_2.next();
System.out.println("tmp.get(key) is :"tmp.get(key));
}
}
}
运行结果如下：
map.get(key) is :ddd
map.get(key) is :bbb
map.get(key) is :ccc
map.get(key) is :aaa
tab.get(key) is :bbb
tab.get(key) is :aaa
tab.get(key) is :ddd
tab.get(key) is :ccc
tmp.get(key) is :aaa
tmp.get(key) is :bbb
tmp.get(key) is :ccc
tmp.get(key) is :cdc
HashMap的结果是没有排序的，而TreeMap输出的结果是排好序的 。
下面就要进入本文的主题了 。先举个例子说明一下怎样使用HashMap:
import java.util.*;
public class Exp1 {
public static void main(String[] args){
HashMap h1=new HashMap();
Random r1=new Random();
for (int i=0;i1000;i){
Integer t=new Integer(r1.nextInt(20));
if (h1.containsKey(t))
((Ctime)h1.get(t)).count;
else
h1.put(t, new Ctime());
}
System.out.println(h1);
}
}
class Ctime{
int count=1;
public String toString(){
return Integer.toString(count);
}
}
在HashMap中通过get()来获取value ， 通过put()来插入value ， ContainsKey()则用来检验对象是否已经存在 。可以看出，和ArrayList的操作相比，HashMap除了通过key索引其内容之外 ， 别的方面差异并不大 。
前面介绍了，HashMap是基于HashCode的，在所有对象的超类Object中有一个HashCode()方法，但是它和equals方法一样，并不能适用于所有的情况 ， 这样我们就需要重写自己的HashCode()方法 。下面就举这样一个例子：
import java.util.*;
public class Exp2 {
public static void main(String[] args){
HashMap h2=new HashMap();
for (int i=0;i10;i)
h2.put(new Element(i), new Figureout());
System.out.println("h2:");
System.out.println("Get the result for Element:");
Element test=new Element(5);
if (h2.containsKey(test))
System.out.println((Figureout)h2.get(test));
else
System.out.println("Not found");
}
}
class Element{
int number;
public Element(int n){
number=n;
}
}
class Figureout{
Random r=new Random();
boolean possible=r.nextDouble()0.5;
public String toString(){
if (possible)
return "OK!";
else
return "Impossible!";
}
}
在这个例子中，Element用来索引对象Figureout,也即Element为key，Figureout为value 。在Figureout中随机生成一个浮点数，如果它比0.5大，打印"OK!"，否则打印"Impossible!" 。之后查看Element(3)对应的Figureout结果如何 。
结果却发现，无论你运行多少次，得到的结果都是"Not found" 。也就是说索引Element(3)并不在HashMap中 。这怎么可能呢？
原因得慢慢来说：Element的HashCode方法继承自Object，而Object中的HashCode方法返回的HashCode对应于当前的地址，也就是说对于不同的对象 ， 即使它们的内容完全相同，用HashCode（）返回的值也会不同 。这样实际上违背了我们的意图 。因为我们在使用 HashMap时，希望利用相同内容的对象索引得到相同的目标对象 ， 这就需要HashCode()在此时能够返回相同的值 。在上面的例子中，我们期望 new Element(i) (i=5)与 Elementtest=newElement(5)是相同的，而实际上这是两个不同的对象，尽管它们的内容相同，但它们在内存中的地址不同 。因此很自然的，上面的程序得不到我们设想的结果 。下面对Element类更改如下
class Element{
int number;
public Element(int n){
number=n;
}
public int hashCode(){
return number;
}
public boolean equals(Object o){
return (o instanceof Element)(number==((Element)o).number);
}
}
在这里Element覆盖了Object中的hashCode()和equals()方法 。覆盖hashCode()使其以number的值作为 hashcode返回，这样对于相同内容的对象来说它们的hashcode也就相同了 。而覆盖equals()是为了在HashMap判断两个key是否相等时使结果有意义（有关重写equals()的内容可以参考我的另一篇文章《重新编写Object类中的方法》） 。修改后的程序运行结果如下：
h2:
Get the result for Element:
Impossible!
请记?。喝绻阆胗行У氖褂肏ashMap，你就必须重写在其的HashCode() 。
还有两条重写HashCode()的原则：
[list=1]
不必对每个不同的对象都产生一个唯一的hashcode，只要你的HashCode方法使get()能够得到put()放进去的内容就可以了 。即"不为一原则" 。
生成hashcode的算法尽量使hashcode的值分散一些，不要很多hashcode都集中在一个范围内 ， 这样有利于提高HashMap的性能 。即"分散原则" 。至于第二条原则的具体原因，有兴趣者可以参考Bruce Eckel的《Thinking in Java》，在那里有对HashMap内部实现原理的介绍 ， 这里就不赘述了 。
掌握了这两条原则，你就能够用好HashMap编写自己的程序了 。不知道大家注意没有，java.lang.Object中提供的三个方法：clone()，equals()和hashCode()虽然很典型 ， 但在很多情况下都不能够适用，它们只是简单的由对象的地址得出结果 。这就需要我们在自己的程序中重写它们 ， 其实java类库中也重写了千千万万个这样的方法 。利用面向对象的多态性——覆盖，Java的设计者很优雅的构建了Java的结构，也更加体现了Java是一门纯OOP语言的特性 。
红黑树，b 树分别用于什么场景，为什么红黑树属于“黑平衡”红黑树代码实现java的二叉树红黑树代码实现java，虽然牺牲了一定的平衡性，但是add、remove操作要由优于AVL树也就是说RB-Tree的“统计性能”更佳红黑树代码实现java！Java中TreeSet，TreeMap的底层都是基于RedBlackTree红黑树的红黑树代码实现java；
B 树主要用在文件系统以及数据库做索引 。比如磁盘存储、文件系统、MySQL数据库
Java中CompareTo()方法的问题楼上正解，应为um.getUserId（）内容已经实现compareTo 接口功能
Java.lang.StringAPI中有定义
compareTo
public int compareTo(String anotherString)按字典顺序比较两个字符串 。该比较基于字符串中各个字符的 Unicode 值 。将此 String 对象表示的字符序列与参数字符串所表示的字符序列进行比较 。如果按字典顺序此 String 对象在参数字符串之前，则比较结果为一个负整数 。如果按字典顺序此 String 对象位于参数字符串之后，则比较结果为一个正整数 。如果这两个字符串相等 ， 则结果为 0；compareTo 只有在方法 equals(Object) 返回 true 时才返回 0 。
红黑树代码实现java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java 红黑树与b树区别、红黑树代码实现java的信息别忘了在本站进行查找喔 。

    推荐阅读


    上一篇：linux查询显卡的命令，linux查看显卡型号命令

    下一篇：内购版的赛车游戏叫什么，内购破解版赛车游戏