Java實現T first（）方法類Hashset <T>

Question

我在以下練習中遇到困難。我不知道接近它的方式。我知道我應該使用某種迭代，但我不確定。我已經能夠用二叉查找樹實現T first（）方法，但不能用HashSet實現。

Add the following method to class HashSet<T> and write a suitable test program. T first() // least value in the set (if the set is empty // throws NoSuchElementException)

import java.util.*; 
    import java.lang.Iterable; 

class HashSet<T extends Comparable<T>> implements Iterable<T> { 

    private LinkedSet<T>[] hashTable; // hash table 


HashSet() { // create the empty set 
    hashTable = (LinkedSet<T>[])(new LinkedSet[1000]); 
               // note coding trick!  
    for (int i=0; i<hashTable.length; i++) 
     hashTable[i] = new LinkedSet<T>(); 

    //Exercise 1 
    int numItems = 0; 
    for (LinkedSet<T> miniSet: hashTable) 
     numItems = numItems+miniSet.size(); 


} 




private int hash(T t) { // hash t into hashTable index 
    return Math.abs(t.hashCode()%hashTable.length); 
} 

int size() {  
    int numItems = 0; 
    for (LinkedSet<T> miniSet: hashTable) 
     numItems = numItems+miniSet.size(); 
    return numItems; 
} 

boolean contains(T t) { 
    return hashTable[hash(t)].contains(t); 
} 

boolean add(T t) { 
    return hashTable[hash(t)].add(t); 
} 

boolean remove(T t) { 
    return hashTable[hash(t)].remove(t); 
} 

//Exercise 3 

    public Iterator<T> iterator() { 
    ArrayList<T> items = new ArrayList<T>(); 
    for (LinkedSet<T> ls: hashTable) 
     for (T t: ls) items.add(t); 
    return items.iterator(); 
} 





    boolean addAll(HashSet<T> ts){ 
    boolean changed = false; 
    for(T i : ts) 
     if(add(i)) 
      changed =true; 
    return true; 
    // add all elements of ts to set; ts is unchanged. 

    } 





} 

import java.util.Iterator; 




public class Prog { 

    public static <T extends Comparable<T>> T first(HashSet<T> hs) 
    // least value in the set (if the set is empty 
    // throws NoSuchElementException 
    { 
     T least = null; 

     for(T i : hs){ 
     if (i.compareTo(least)<0){ 
     i = least; 
     } 

    } 
     return least; 
    } 

import java.util.List; 


    public class main1 { 

    public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    HashSet<String> test1 = new HashSet<String>(); 
    test1.add("sean"); 
    test1.add("adam"); 
    test1.add("ava"); 

    HashSet<Integer> test2 = new HashSet<Integer>(); 
    test2.add(2); 
    test2.add(10); 
    test2.add(5); 

    System.out.println(test1.size()); 

    System.out.println(Prog.first(test2)); 


    } 

} 

Answer 1

您可以：

• 迭代通過值：嘗試（T X：the_set）...

• 拿分：拿第一，一個迭代，如果新是少的，拿它

• retu RN該值（或者，如果異常沒有值）

嘗試完成這個

public static <T> T first(HashSet<T> _ht) 
{ 
// if _ht empty throws an exception 
// TODO 

// Take the first (or any element) 
// TODO 
T least; 

for (T one_element: _ht) 
    { 
    // compare one_element and least 
    // TODO 
    // and keep the least ! 
    } 

return least; 
} 

Answer 2

我同意彼得的評論，一個HashSet沒有的「第一」或「最後」的理念，因爲它沒有訂購。然而，類TreeSet，它實現SortedSet。

元素類型必須定義自然順序（例如int或Comparable<T>），否則必須提供Comparator<T>到樹集合的構造函數。

實施例：

Integer[] numbers = { 5, 9, 1, 11 }; 
TreeSet<Integer> set = new TreeSet<>(Arrays.asList(numbers)); 
Integer least = set.first(); // 1 

---

一種可能的實現的方法first()（假設二叉樹）：

public T first() { 
    Node<T> p = root; 
    if (p != null) { 
     while (p.left != null) { // not "while (p != null)" 
      p = p.left; 
     } 
    } 
    return p == null ? null : p.item; 
}