黑马程序员技术交流社区

标题: Hashable、HashMap和HashSet，TreeSet 有什么区别？ [打印本页]

作者: prospect 时间: 2012-4-27 22:55
标题: Hashable、HashMap和HashSet，TreeSet 有什么区别？
Hashable、HashMap和HashSet，TreeSet 有什么区别？请教一下，总是分布明白？

作者: 赵嘉男 时间: 2012-4-27 22:59
Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现
  HashMap允许将null作为一个entry的key或者value，而Hashtable不允许
  还有就是，HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。
  最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在
多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap
就必须为之提供外同步。
Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差异
HashSet无序
TreeSet有序
二者里边不能有重复的对象

作者: 胡生蒙 时间: 2012-4-27 23:30
HashSet:底层数据结构是哈希表。是线程不安全的。不同步。
HashSet是如何保证元素唯一性的呢？
是通过元素的两个方法，hashCode和equals来完成。
如果元素的HashCode值相同，才会判断equals是否为true。
如果元素的hashcode值不同，不会调用equals。
注意,对于判断元素是否存在，以及删除等操作，依赖的方法是元素的 hashcode和equals方法。
|--TreeSet：可以对Set集合中的袁术进行排序。底层数据结构是二叉树。
保证元素的唯一性的依据：compareTo()方法return 0.

TreeSet排序的第一种方式：让元素自身具备比较性。元素需要实现Comparable接口，覆盖compareTo()方法。这种方式也称为元素的自然顺序，或者叫做默认顺序。

当元素自身不具备比较性，或者具备的比较性不是所需要的。
这时需要让容器自身具备比较性。
定义了比较器，将比较器对象作为参数传递给TreeSet集合的构造函数。
当两种排序都存在时，以比较器为主。
定义一个类，实现Comparator接口，覆盖compare方法。
Set集合的功能和Collection是一致的。

|--Hashtable：底层是哈希表数据结构，不可以存入null键null值，该集合是线程同步的。Jdk1.0 效率低。
|--HashMap：底层是哈希表数据结构，允许使用null键和null值，该集合是线程不同步的。Jdk2.0 效率高。
①：调用put()方法添加元素时，如果有相同的key，那么后添加的值会覆盖原有key对应的值，并且put()方法会返回被覆盖的值。

作者: 光sail 时间: 2012-4-27 23:32
HashSet扩展AbstractSet并且实现Set接口。它创建一个类集，该类集使用散列表进行存储。无法像TreeSet那样进行升序存储。

import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class MapTest
{
public static void main(String[] args)
{
HashMap map = new HashMap();
map.put("a", "aa");
map.put("b", "bb");
map.put("c", "cc");
map.put("d", "dd");
map.put("e", "ee");
Set set = map.keySet();
for(Iterator iter = set.iterator(); iter.hasNext();)
{
String key = (String)iter.next();
String value = (String)map.get(key);
System.out.println(key + "=" + value);
}
}
}

复制代码

打印输出为
d=dd
e=ee
b=bb
c=cc
a=aa
如上面解释的那样，元素并没有按顺序进行存储
TreeSet为使用树来进行存储的Set接口提供了一个工具，对象按升序存储。访问和检索是很快的。在存储了大量的需要进行快速检索的排序信息的情况下，TreeSet是一个很好的选择

import java.util.TreeSet;
public class TreeSetTest
{
public static void main(String[] args)
{
TreeSet set = new TreeSet();
set.add("C");
set.add("A");
set.add("B");
set.add("E");
set.add("F");
set.add("D");
System.out.println(set);
}
}

复制代码

打印输出为 [A, B, C, D, E, F]
正如上面解释的那样，因为TreeSet按树存储其
元素，它们被按照排序次序自动安排，如程序
输出所示

HashMap类使用散列表实现Map接口。这允许一些基本操作如get( )和put( )的运行时间保持恒定，即便对大型集合，也是这样的

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
public class MapTest
{
public static void main(String[] args)
{
HashMap map = new HashMap();
map.put("a", "aa");
map.put("b", "bb");
map.put("c", "cc");
map.put("d", "dd");
Set set = map.entrySet();
for(Iterator iter = set.iterator(); iter.hasNext();)
{
Map.Entry entry = (Map.Entry)iter.next();
String key = (String)entry.getKey();
String value = (String)entry.getValue();
System.out.println(key + " : " + value);
}

复制代码

打印输出为
d : dd
b : bb
c : cc
a : aa

程序开始创建一个散列映射，然后将名字的映射增加到表中。接下来，映射的内容通过使用由调用函数entrySet( )而获得的集合“视图”而显示出来。关键字和值通过调用由Map.Entry定义的getKey( )和getValue( )方法而显示。

•TreeMap类通过使用树实现Map接口。
TreeMap提供了按排序顺序存储关键字/值对的有效手段，同时允许快速检索。应该注意的是，不像散列映射，树映射保证它的元素按照关键字升序排序

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;
public class TreeSetTest
{
public static void main(String[] args)
{
TreeSet set = new TreeSet(new PersonComparator());
Person p1 = new Person(10);
Person p2 = new Person(20);
Person p3 = new Person(30);
Person p4 = new Person(40);
set.add(p1);
set.add(p2);
set.add(p3);
set.add(p4);
for(Iterator iter = set.iterator(); iter.hasNext();)
{
Person p = (Person)iter.next();
System.out.println(p.score);
}
}
}
class Person
{
int score;
public Person(int score)
{
this.score = score;
}
public String toString()
{
return String.valueOf(this.score);
}
}
class PersonComparator implements Comparator
{
public int compare(Object arg0, Object arg1)
{
Person p1 = (Person) arg0;
Person p2 = (Person) arg1;
return p2.score - p1.score;
}
}

复制代码

打印输出
40
30
20
10
注意：对关键字进行了排序。可以通过在创建映射时，指定一个比较函数来改变排序

作者: 周海诚 时间: 2012-4-28 14:02
1. HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key
2. Map的key和Set都有一个共同的特性就是集合的唯一性.TreeMap更是多了一个排序的功能.
3. hashCode和equal()是HashMap用的, 因为无需排序所以只需要关注定位和唯一性即可.
hashCode是用来计算hash值的,hash值是用来确定hash表索引的.
hash表中的一个索引处存放的是一张链表, 所以还要通过equal方法循环比较链上的每一个对象才可以真正定位到键值对应的Entry.
put时,如果hash表中没定位到,就在链表前加一个Entry,如果定位到了,则更换Entry中的value,并返回旧value
4. 由于TreeMap需要排序,所以需要一个Comparator为键值进行大小比较.当然也是用Comparator定位的.
Comparator可以在创建TreeMap时指定
如果创建时没有确定,那么就会使用key.com

作者: 崔仁军 时间: 2012-4-28 14:21
1.  HashSet 底层是使用 HashMap 实现的。当使用add 方法将对象添加到Set  当中时，
实际上是将该对象作为底层所维护的Map 对象的key，而value 则都是同一个Object
对象（该对象我们用不上）；
2.  HashMap 底层维护一个数组，我们向HashMap 中所放置的对象实际上是存储在该数
组当中;当向HashMap  中put 一对键值时，它会根据key  的hashCode 值计算出一个位置，
该位置就是此对象准备往数组中存放的位置。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2