文章
开始
开始学习
JavaRush /Java 博客 /Random-ZH /Java 中的哈希集
渚古河
第 30 级
Москва

Java 中的哈希集

已在 Random-ZH 群组中发布
该类HashSet实现接口Set，基于哈希表，并且由实例支持HashMap。由于HashSet元素没有排序，因此不能保证在一段时间后元素的顺序相同。只要哈希函数正确地将元素分配到“桶”中，添加、删除和搜索操作就会在常数时间内完成，这将在后面讨论。 Java 中的哈希集 - 1关于以下几个要点HashSet：
  • 因为 该类实现了接口Set，它只能存储唯一值；
  • 可以存储NULL值；
  • 元素添加的顺序是使用哈希码计算的；
  • HashSet还实现了Serializable和Cloneable。
为了保持操作的执行时间恒定， , 操作所花费的时间必须与 中的元素数量+ 内置实例的“容量” （“篮子”数量）HashSet成正比。因此，为了保持性能，重要的是不要将初始容量设置得太高（或负载因子太低）。初始容量 – 哈希表中单元（“bin”）的初始数量。如果所有单元格都被填满，它们的数量将自动增加。负载系数是衡量其容量自动增加之前的满载程度的指标。当 中的元素数量大于初始容量与负载因子的乘积时，哈希表将被重新哈希（重新计算元素的哈希码，并根据获得的值重建表），并且数量其中的细胞数量增加了一倍。 负载因子 = 表中存储的元素数量 / 哈希表大小 例如，如果表中的初始单元格数量为 16，负载因子为 0.75，则当填充的单元格数量达到 12 时，细胞数量会自动增加。负载系数和初始容量是影响性能的两个主要因素。0.75 的负载因子可提供良好的平均性能。如果增大该参数，那么内存负载将会减少（因为它会减少重新哈希和重建的次数），但会影响追加和查找操作。为了最大限度地减少重新散列所花费的时间，您需要选择正确的初始容量参数。如果初始容量大于最大元素数除以负载因子，则根本不会发生重新哈希操作。 HashSetHashMapHashSetHashSetHashSet重要的：HashSet不是一种具有内置同步功能的数据结构，因此如果多个线程同时对其进行操作，并且至少其中一个线程试图进行更改，则有必要从外部提供同步访问。这通常是以另一个封装HashSet. 如果不存在这样的对象，则Collections.synchronizedSet(). 这是目前防止与HashSet.
Java-университет 
Set s = Collections.synchronizedSet(new HashSet(...));
哈希集构造函数：
  1. HashSet h = new HashSet(); - 默认构造函数。默认初始容量为16，负载系数为0.75。
  2. HashSet h = new HashSet(int initialCapacity)– 具有给定初始容量的构造函数。负载系数 – 0.75。
  3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— 具有给定初始容量和负载系数的构造函数。
  4. HashSet h = new HashSet(Collection C)– 添加另一个集合中的元素的构造函数。
下面的代码演示了一些方法HashSet： 
import java.util.*;

class Test
{
    public static void main(String[]args)
    {
        HashSet<String> h = new HashSet<String>();

        // Add elements to the HashSet using the add() method
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// try to add another same element

        // Print the elements of the HashSet to the console
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Remove elements from the set using the remove() method
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Loop through the elements of the HashSet using an iterator:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}
结论： 
[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India
所有实现接口的类Set都由实现内部支持Map。HashSet使用 存储元素HashMap。尽管HashMap元素必须表示为键值对才能添加元素，但 HashSet仅添加值。事实上，我们传递给对象的值HashSet是对象的键HashMap，并且使用一个常量作为值HashMap。这样，在每个键值对中，所有键都将具有相同的值。 实施HashSet于java doc： 
private transient HashMap map;

// Constructor - 1
// All constructors implicitly create a HashMap object.
public HashSet()
{
    // Create an implicit HashMap object
    map = new HashMap();
}

// Constructor- 2
public HashSet(int initialCapacity)
{
    // Create an implicit HashMap object
    map = new HashMap(initialCapacity);
}

// An object of the Object class, each time acting as a value in the HashMap
private static final Object PRESENT = new Object();
如果你看一下方法add()y HashSet： 
public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}
您可以注意到方法add()y调用内部对象上的HashSet方法，将要添加的元素作为键传递给它，并将 PRESENT 常量作为值传递给它。该方法的工作原理类似。它调用内部对象方法： put()HashMapremove()remove()HashMap 
public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}
HashSet基于哈希表，添加、删除或查找操作平均将在常数 (O(1)) 时间内完成。 方法HashSet：
  1. boolean add(E e)：向 中添加一个元素HashSet，如果没有，但如果这样的元素已经存在，则该方法返回false。
  2. void clear():从集合中删除所有元素。
  3. boolean contains(Object o)：如果给定元素存在于集合中，则返回true 。
  4. boolean remove(Object o)：从集合中删除给定元素（如果存在）。
  5. Iterator iterator()：返回集合元素的迭代器。
  6. boolean isEmpty()：如果集合中没有元素，则返回true 。
  7. Object clone()：执行表面克隆HashSet。
Javadoc：https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html
评论
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION