本文共 8533 字，大约阅读时间需要 28 分钟。

《Java语言程序设计与数据结构》编程练习答案（第二十七章）（一）

英文名：Introduction to Java Programming and Data Structures, Comprehensive Version, 11th Edition

27.1

public class book {
       public static void main(String[] args) {
           Scanner input = new Scanner(System.in);    }}interface MyMap
   
    {
       public void clear();    public boolean containsKey(K key);    public boolean containsValue(V value);    public Set
    
     
      > entrySet();    public V get(K key);    public boolean isEmpty();    public Set
      
        keySet();    public V put(K key, V value);    public void remove(K key);    public int size();    public Set
       
         values();    public static class Entry
        
         { K key; V value; public Entry(K key, V value){ this.key = key; this.value = value; } public K getKey(){ return key; } public V getValue(){ return value; } @Override public String toString(){ return "[" + key +", " + value + "]"; } }}class MyHashMap
         
           implements MyMap
          
           { private static int DEFAULT_INITIAL_CAPACITY = 4; private static int MAXIMUM_CAPACITY = 1 << 30; private int capacity; private static float DEFAULT_MAX_LOAD_FACTOR = 0.5f; private float loadFactorThreshold; private int size = 0; Entry
           
            [] table; public MyHashMap(){ this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR); } public MyHashMap(int initialCapacity){ this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR); } public MyHashMap(int initialCapacity, float loadFactorThreshold){ if(initialCapacity > MAXIMUM_CAPACITY) this.capacity = MAXIMUM_CAPACITY; else this.capacity = trimToPowerOfTwo(initialCapacity); this.loadFactorThreshold = loadFactorThreshold; table = new Entry[capacity]; } @Override public void clear() { for(int i=0;i
            
             > entrySet() { Set
             
              
               > set = new HashSet<>(); for(int i=0;i
               
                 keySet() { Set
                
                  set = new HashSet<>(); for(int i=0;i
                 
                  (key, value); size++; if(size > capacity * loadFactorThreshold){ rehash(); } return value; } else{ if(table[insertIndex].getKey().equals(key)){ V oldValue = table[insertIndex].getValue(); table[insertIndex].value = value; return oldValue; } else{ insertIndex = (insertIndex + 1) % capacity; } } } } @Override public void remove(K key) { int startIndex = hash(key.hashCode()); while(table[startIndex] != null){ if(table[startIndex].getKey().equals(key)){ table[startIndex] = null; size--; break; } startIndex++; } } @Override public int size() { return size; } @Override public Set
                  
                    values() { Set
                   
                     set = new HashSet<>(); for(int i=0;i
                    
                     > set = entrySet(); capacity <<= 1; table = new Entry[capacity]; size = 0; for(Entry
                     
                       entry: set){ put(entry.getKey(), entry.getValue()); } }}
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

27.2

public class book {
       public static void main(String[] args) {
           Scanner input = new Scanner(System.in);    }}interface MyMap
   
    {
       public void clear();    public boolean containsKey(K key);    public boolean containsValue(V value);    public Set
    
     
      > entrySet();    public V get(K key);    public boolean isEmpty();    public Set
      
        keySet();    public V put(K key, V value);    public void remove(K key);    public int size();    public Set
       
         values();    public static class Entry
        
         { K key; V value; public Entry(K key, V value){ this.key = key; this.value = value; } public K getKey(){ return key; } public V getValue(){ return value; } @Override public String toString(){ return "[" + key +", " + value + "]"; } }}class MyHashMap
         
           implements MyMap
          
           { private static int DEFAULT_INITIAL_CAPACITY = 4; private static int MAXIMUM_CAPACITY = 1 << 30; private int capacity; private static float DEFAULT_MAX_LOAD_FACTOR = 0.5f; private float loadFactorThreshold; private int size = 0; Entry
           
            [] table; public MyHashMap(){ this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR); } public MyHashMap(int initialCapacity){ this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR); } public MyHashMap(int initialCapacity, float loadFactorThreshold){ if(initialCapacity > MAXIMUM_CAPACITY) this.capacity = MAXIMUM_CAPACITY; else this.capacity = trimToPowerOfTwo(initialCapacity); this.loadFactorThreshold = loadFactorThreshold; table = new Entry[capacity]; } @Override public void clear() { for(int i=0;i
            
             > entrySet() { Set
             
              
               > set = new HashSet<>(); for(int i=0;i
               
                 keySet() { Set
                
                  set = new HashSet<>(); for(int i=0;i
                 
                  (key, value); size++; if(size > capacity * loadFactorThreshold){ rehash(); } return value; } else{ if(table[insertIndex].getKey().equals(key)){ V oldValue = table[insertIndex].getValue(); table[insertIndex].value = value; return oldValue; } else{ insertIndex = (insertIndex + jump*jump) % capacity; jump++; } } } } @Override public void remove(K key) { int startIndex = hash(key.hashCode()); int jump = 1; while(table[startIndex] != null){ if(table[startIndex].getKey().equals(key)){ table[startIndex] = null; size--; break; } startIndex = (startIndex + jump*jump) % capacity; jump++; } } @Override public int size() { return size; } @Override public Set
                  
                    values() { Set
                   
                     set = new HashSet<>(); for(int i=0;i
                    
                     > set = entrySet(); capacity <<= 1; table = new Entry[capacity]; size = 0; for(Entry
                     
                       entry: set){ put(entry.getKey(), entry.getValue()); } }}
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

27.3

public class book {
       public static void main(String[] args) {
           Scanner input = new Scanner(System.in);    }}interface MyMap
   
    {
       public void clear();    public boolean containsKey(K key);    public boolean containsValue(V value);    public Set
    
     
      > entrySet();    public V get(K key);    public boolean isEmpty();    public Set
      
        keySet();    public V put(K key, V value);    public void remove(K key);    public int size();    public Set
       
         values();    public static class Entry
        
         { K key; V value; public Entry(K key, V value){ this.key = key; this.value = value; } public K getKey(){ return key; } public V getValue(){ return value; } @Override public String toString(){ return "[" + key +", " + value + "]"; } }}class MyHashMap
         
           implements MyMap
          
           { private static int DEFAULT_INITIAL_CAPACITY = 4; private static int MAXIMUM_CAPACITY = 1 << 30; private int capacity; private static float DEFAULT_MAX_LOAD_FACTOR = 0.5f; private float loadFactorThreshold; private int size = 0; Entry
           
            [] table; public MyHashMap(){ this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR); } public MyHashMap(int initialCapacity){ this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR); } public MyHashMap(int initialCapacity, float loadFactorThreshold){ if(initialCapacity > MAXIMUM_CAPACITY) this.capacity = MAXIMUM_CAPACITY; else this.capacity = trimToPowerOfTwo(initialCapacity); this.loadFactorThreshold = loadFactorThreshold; table = new Entry[capacity]; } @Override public void clear() { for(int i=0;i
            
             > entrySet() { Set
             
              
               > set = new HashSet<>(); for(int i=0;i
               
                 keySet() { Set
                
                  set = new HashSet<>(); for(int i=0;i
                 
                  (key, value); size++; if(size > capacity * loadFactorThreshold){ rehash(); } return value; } else{ if(table[insertIndex].getKey().equals(key)){ V oldValue = table[insertIndex].getValue(); table[insertIndex].value = value; return oldValue; } else{ insertIndex = (insertIndex + insertIndex) % capacity; } } } } @Override public void remove(K key) { int startIndex = hash(key.hashCode()); while(table[startIndex] != null){ if(table[startIndex].getKey().equals(key)){ table[startIndex] = null; size--; break; } startIndex = (startIndex + startIndex) % capacity; } } @Override public int size() { return size; } @Override public Set
                  
                    values() { Set
                   
                     set = new HashSet<>(); for(int i=0;i
                    
                     > set = entrySet(); capacity <<= 1; table = new Entry[capacity]; size = 0; for(Entry
                     
                       entry: set){ put(entry.getKey(), entry.getValue()); } }}
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

27.4

public V xPut(K key, V value){
           int insertIndex = hash(key.hashCode());        while(table[insertIndex] != null){
               insertIndex++;        }        table[insertIndex] = new Entry<>(key, value);        size++;        if(size > capacity * loadFactorThreshold){
               rehash();        }        return value;    }    public Set
   
     getAll(K key){
           Set
    
      ret = new HashSet<>();                int startIndex = hash(key.hashCode());        while(table[startIndex] != null){
               ret.add(table[startIndex].getValue());            startIndex = (startIndex + 1) % capacity;        }                return ret;    }
    
   

转载地址：http://npzai.baihongyu.com/