HashTableMap

java.lang.Object
- net.datastructures.HashTableMap<K,V>

All Implemented Interfaces:

Map<K,V>

Direct Known Subclasses:

AdjacencyListGraph.MyPosition
```
public class HashTableMap<K,V>
extends java.lang.Object
implements Map<K,V>
```
A hash table data structure that uses linear probing to handle collisions. The hash function uses the built-in hashCode method and the multiply-add-and-divide method. The load factor is alwyas kept less than or equal to 0.5. When the load factor reaches 0.5, the entries are rehashed into a new bucket array with twice the capacity.

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

static class HashTableMap.HashEntry<K,V>
Nested class for an entry in a hash table.

Nested Classes
Modifier and Type	Class and Description
`static class`	`HashTableMap.HashEntry<K,V>` Nested class for an entry in a hash table.

Field Summary

Fields
Modifier and Type	Field and Description
`protected Entry<K,V>`	`AVAILABLE`
`protected Entry<K,V>[]`	`bucket`
`protected int`	`capacity`
`protected int`	`n`
`protected int`	`prime`
`protected long`	`scale`
`protected long`	`shift`

Constructor Summary

Constructors
Constructor and Description
`HashTableMap()` Creates a hash table with prime factor 109345121 and capacity 1000.
`HashTableMap(int cap)` Creates a hash table with prime factor 109345121 and given capacity.
`HashTableMap(int p, int cap)` Creates a hash table with the given prime factor and capacity.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`protected void`	`checkKey(K k)` Determines whether a key is valid.
`java.lang.Iterable<Entry<K,V>>`	`entries()` Returns an iterable object containing all of the entries.
`protected int`	`findEntry(K key)` Helper search method - returns index of found key or -(a + 1), where a is the index of the first empty or available slot found.
`V`	`get(K key)` Returns the value associated with a key.
`int`	`hashValue(K key)` Hash function applying MAD method to default hash code.
`boolean`	`isEmpty()` Returns whether or not the table is empty.
`java.lang.Iterable<K>`	`keys()` Returns an iterable object containing all of the keys.
`V`	`put(K key, V value)` Put a key-value pair in the map, replacing previous one if it exists.
`protected void`	`rehash()` Doubles the size of the hash table and rehashes all the entries.
`V`	`remove(K key)` Removes the key-value pair with a specified key.
`int`	`size()` Returns the number of entries in the hash table.
`java.lang.Iterable<V>`	`values()` Returns an iterable object containing all of the values.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - AVAILABLE
```
protected Entry<K,V> AVAILABLE
```
  - n
```
protected int n
```
  - prime
```
protected int prime
```
  - capacity
```
protected int capacity
```
  - bucket
```
protected Entry<K,V>[] bucket
```
  - scale
```
protected long scale
```
  - shift
```
protected long shift
```
- Constructor Detail
  - HashTableMap
```
public HashTableMap()
```
    Creates a hash table with prime factor 109345121 and capacity 1000.
  - HashTableMap
```
public HashTableMap(int cap)
```
    Creates a hash table with prime factor 109345121 and given capacity.
  - HashTableMap
```
public HashTableMap(int p,
                    int cap)
```
    Creates a hash table with the given prime factor and capacity.
- Method Detail
  - checkKey
```
protected void checkKey(K k)
```
    Determines whether a key is valid.
  - hashValue
```
public int hashValue(K key)
```
    Hash function applying MAD method to default hash code.
  - size
```
public int size()
```
    Returns the number of entries in the hash table.
    
    Specified by:
    
    size in interface Map<K,V>
  - isEmpty
```
public boolean isEmpty()
```
    Returns whether or not the table is empty.
    
    Specified by:
    
    isEmpty in interface Map<K,V>
  - keys
```
public java.lang.Iterable<K> keys()
```
    Returns an iterable object containing all of the keys.
    
    Specified by:
    
    keys in interface Map<K,V>
  - findEntry
```
protected int findEntry(K key)
                 throws InvalidKeyException
```
    Helper search method - returns index of found key or -(a + 1), where a is the index of the first empty or available slot found.
    
    Throws:
    
    InvalidKeyException
  - get
```
public V get(K key)
      throws InvalidKeyException
```
    Returns the value associated with a key.
    
    Specified by:
    
    get in interface Map<K,V>
    
    Throws:
    
    InvalidKeyException
  - put
```
public V put(K key,
             V value)
      throws InvalidKeyException
```
    Put a key-value pair in the map, replacing previous one if it exists.
    
    Specified by:
    
    put in interface Map<K,V>
    
    Throws:
    
    InvalidKeyException
  - rehash
```
protected void rehash()
```
    Doubles the size of the hash table and rehashes all the entries.
  - remove
```
public V remove(K key)
         throws InvalidKeyException
```
    Removes the key-value pair with a specified key.
    
    Specified by:
    
    remove in interface Map<K,V>
    
    Throws:
    
    InvalidKeyException
  - entries
```
public java.lang.Iterable<Entry<K,V>> entries()
```
    Returns an iterable object containing all of the entries.
    
    Specified by:
    
    entries in interface Map<K,V>
  - values
```
public java.lang.Iterable<V> values()
```
    Returns an iterable object containing all of the values.
    
    Specified by:
    
    values in interface Map<K,V>

Class HashTableMap<K,V>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

AVAILABLE

n

prime

capacity

bucket

scale

shift

Constructor Detail

HashTableMap

HashTableMap

HashTableMap

Method Detail

checkKey

hashValue

size

isEmpty

keys

findEntry

get

put

rehash

remove

entries

values