本文共 3233 字,大约阅读时间需要 10 分钟。
原文地址:
HashSet:
HashSet的构造函数:
HashSet h = new HashSet(); 默认初始化大小是16,默认装载因子是0.75. HashSet h = new HashSet(int initialCapacity); 默认装载因子是0.75 HashSet h = new HashSet(int initialCapacity, float loadFactor); HashSet h = new HashSet(Collection C);
什么是初始化大小与装载因子:
初始化尺寸就是当创建哈希表(HashSet内部用哈希表的数据结构)的时候桶(buckets)的数量。如果当前的尺寸已经满了,那么桶的数量会自动增长。
装载因子衡量的是在HashSet自动增长之前允许有多满。当哈希表中实体的数量已经超出装载因子与当前容量的积,那么哈希表就会再次进行哈希(也就是内部数据结构重建),这样哈希表大致有两倍桶的数量。
表中已经存储的元素的数量 装载因子 = ----------------------------------------- 哈希表的大小
例如:如果内部容量为16,装载因子为0.75,那么当表中有12个元素的时候,桶的数量就会自动增长。
性能影响:
装载因子和初始化容量是影响HashSet操作的两个主要因素。装载因子为0.75的时候可以提供关于时间和空间复杂度方面更有效的性能。如果我们加大这个装载因子,那么内存的上限就会减小(因为它减少了内部重建的操作),但是将影响哈希表中的add与查询的操作。为了减少再哈希操作,我们应该选择一个合适的初始化大小。如果初始化容量大于实体的最大数量除以装载因子,那么就不会有再哈希的动作发生了。
HashSet中的一些重要方法:
简单的程序:
// Java program to demonstrate working of HashSetimport java.util.*;class Test{ public static void main(String[]args) { HashSeth = new HashSet (); // adding into HashSet h.add("India"); h.add("Australia"); h.add("South Africa"); h.add("India");// adding duplicate elements // printing HashSet System.out.println(h); System.out.println("List contains India or not:" + h.contains("India")); // Removing an item h.remove("Australia"); System.out.println("List after removing Australia:"+h); // Iterating over hash set items System.out.println("Iterating over list:"); Iterator i = h.iterator(); while (i.hasNext()) System.out.println(i.next()); }}
上述代码的输出:
[Australia, South Africa, India]List contains India or not:trueList after removing Australia:[South Africa, India]Iterating over list:South AfricaIndia
HashSet内部是如何工作的?
所有Set接口的类内部都是由Map做支撑的。HashSet用HashMap对它的内部对象进行排序。你一定好奇输入一个值到HashMap,我们需要的是一个键值对,但是我们传给HashSet的是一个值。
那么HashMap是如何排序的?
实际上我们插入到HashSet中的值在map对象中起的是键的作用,因为它的值Java用了一个常量。所以在键值对中所有的键的值都是一样的。
如果我们在Java Doc中看一下HashSet的实现,大致是这样的:
private transient HashMap map;// Constructor - 1// All the constructors are internally creating HashMap Object.public HashSet(){ // Creating internally backing HashMap object map = new HashMap<>();}// Constructor - 2public HashSet(int initialCapacity){ // Creating internally backing HashMap object map = new HashMap<>(initialCapacity);}// Dummy value to associate with an Object in Mapprivate static final Object PRESENT = new Object();
如果我们看下HashSet中的add方法:
public boolean add(E e){ return map.put(e, PRESENT) == null;}
我们可以注意到,HashSet类的add()方法内部调用的是HashMap的put()方法,通过你指定的值作为key,常量“PRESENT”作为值传过去。
remove()也是用类似的方法工作。它内部调用的是Map接口的remove。
public boolean remove(Object o){ return map.remove(o) == PRESENT;}
HashSet操作的时间复杂度:
HashSet底层的数据结构是哈希表,所以HashSet的add,remove与查询(包括contain方法)的分摊(平均或者一般情况)时间复杂度是O(1)。
参考文献:
转载地址:http://skhii.baihongyu.com/