Hashtable brief introduction

Hashtable It is also based on hash table , Again, each element is a key-value Yes , Its interior also solves the conflict problem through the single chain table , Capacity is insufficient ( The threshold is exceeded ) when , It will also grow automatically .Hashtable It's also JDK1.0 Introduced classes , It's thread safe , It can be used in multithreaded environment .Hashtable It's also implemented Serializable Interface , It supports serialization , Realized Cloneable Interface , Can be cloned .HashTable Of Value It can't be null. The default size is 11,HashMap The default size is 16.

HashTable Source analysis

Hashtable Key variables of

 // preservation key-value Array of .
//Hashtable Single linked list is also used to solve conflicts , every last Entry It's essentially a one-way list
private transient Entry[] table;
//Hashtable Number of middle key value pairs
private transient int count;
// threshold , To determine if adjustments are needed Hashtable The capacity of (threshold = Capacity * Load factor )
private int threshold;
// Load factor
private float loadFactor;
//Hashtable The number of changes , be used for fail-fast Implementation of mechanism
private transient int modCount = 0;
// Serial version number
private static final long serialVersionUID = 1421746759512286392L;

Data nodes Entry Data structure of

private static class Entry<K,V> implements Map.Entry<K,V> {
// Hash value
int hash;
K key;
V value;
// Next to Entry, The next node of the linked list
Entry<K,V> next; // Constructors
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
} protected Object clone() {
return new Entry<K,V>(hash, key, value,
(next==null ? null : (Entry<K,V>) next.clone()));
} public K getKey() {
return key;
} public V getValue() {
return value;
} // Set up value. if value yes null, Throw an exception .
public V setValue(V value) {
if (value == null)
throw new NullPointerException(); V oldValue = this.value;
this.value = value;
return oldValue;
} // Cover equals() Method , Whether two Entry Whether it is equal or not .
// If two Entry Of key and value All equal , They are considered equal .
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o; return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
} public int hashCode() {
return hash ^ (value==null ? 0 : value.hashCode());
} public String toString() {
return key.toString()+"="+value.toString();
}
}

HashTable Constructors in :

// Appoint “ Capacity size ” and “ Load factor ” Constructor for 
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity<0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
if (loadFactor <= 0||Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor); if(initialCapacity==0)
initialCapacity = 1;
this.loadFactor=loadFactor;
table = new Entry[initialCapacity];
threshold=(int)(initialCapacity * loadFactor);
}
// Appoint “ Capacity size ” Constructor for
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
// Default constructor .
public Hashtable() {
// Default constructor , The specified capacity size is 11; Load factor is 0.75
this(11, 0.75f);
}
// contain “ Son Map” Constructor for
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
// take “ Son Map” All elements of are added to Hashtable in
putAll(t);
}

Hashtable Realization java.io.Serializable, The serial reading is realized respectively 、 Write function . Serial write function is to write Hashtable Of “ Total capacity , Actual capacity , be-all Entry” All are written to the output stream and the serial read function : According to the writing mode, read out will Hashtable Of “ Total capacity , Actual capacity , be-all Entry” Read out in turn .

private synchronized void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
// Write out the length, threshold, loadfactor
s.defaultWriteObject(); // Write out length, count of elements and then the key/value objects
s.writeInt(table.length);
s.writeInt(count);
for (int index = table.length-1; index >= 0; index--) {
Entry entry = table[index]; while (entry != null) {
s.writeObject(entry.key);
s.writeObject(entry.value);
entry = entry.next;
}
}
} private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// Read in the length, threshold, and loadfactor
s.defaultReadObject(); // Read the original length of the array and number of elements
int origlength = s.readInt();
int elements = s.readInt(); // Compute new size with a bit of room 5% to grow but
// no larger than the original size. Make the length
// odd if it's large enough, this helps distribute the entries.
// Guard against the length ending up zero, that's not valid.
int length = (int)(elements * loadFactor) + (elements / 20) + 3;
if (length > elements && (length & 1) == 0)
length--;
if (origlength > 0 && length > origlength)
length = origlength; Entry[] table = new Entry[length];
count = 0; // Read the number of elements and then all the key/value objects
for (; elements > 0; elements--) {
K key = (K)s.readObject();
V value = (V)s.readObject();
// synch could be eliminated for performance
reconstitutionPut(table, key, value);
}
this.table = table;
}

Hashtable Realized Cloneable Interface , It is realized. clone() Method .clone() The method is simple , It's about cloning one Hashtable Object and return .

// Clone a Hashtable, And Object Form return of .
public synchronized Object clone() {
try {
Hashtable<K,V> t = (Hashtable<K,V>) super.clone();
t.table = new Entry[table.length];
for (int i = table.length ; i-- > 0 ; ) {
t.table[i] = (table[i] != null)
? (Entry<K,V>) table[i].clone() : null;
}
t.keySet = null;
t.entrySet = null;
t.values = null;
t.modCount = 0;
return t;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}

put() Method direction hasttable Add elements to it .

 // take “key-value” Add to Hashtable in 
public synchronized V put(K key, V value) {
// Hashtable You can't insert value by null The elements of !!!
if (value == null) {
throw new NullPointerException();
} // if “Hashtable The key already exists in the key The key/value pair ”,
// Then use “ new value” Replace “ old value”
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
} // if “Hashtable There is no key in key The key/value pair ”,
// take “ Modify Statistics ”+1
modCount++;
// if “Hashtable Actual capacity ” > “ threshold ”( threshold = Total capacity * Load factor )
// Then adjust Hashtable Size
if (count >= threshold) {
rehash(); tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
} // New key-value Yes, insert into tab[index] It's about ( That is, the head node of the linked list )
Entry<K,V> e = tab[index];
tab[index] = new Entry<K,V>(hash, key, value, e);
count++;
return null;
}

remove() Delete hashtable The middle key is key The elements of .

 public synchronized V remove(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length; // from table[index] Find the node to be deleted in the linked list , And delete the node .
// Because it's a single chain watch , So keep the previous node with the deleted node , To effectively delete nodes
for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null;
}

Rehash(), Change the length of the array to double and one .

 // adjustment Hashtable The length of , Change the length to the original 2 times +1
protected void rehash() {
int oldCapacity = table.length;
Entry[] oldMap = table; // Create a new capacity of Entry Array
int newCapacity = oldCapacity * 2 + 1;
Entry[] newMap = new Entry[newCapacity]; modCount++;
threshold = (int)(newCapacity * loadFactor);
table = newMap; // take “ old Hashtable” The elements in are copied to “ new Hashtable” in
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
// Recalculate index
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}

containsKey() It's the role of judgment Hashtable Does it include key

public synchronized boolean containsKey(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
// Calculate index value ,
// % tab.length The goal is to prevent data from crossing boundaries
int index = (hash & 0x7FFFFFFF) % tab.length;
// find “key Corresponding Entry( Linked list )”, Then find out in the list “ Hash value ” and “ Key value ” And key All equal elements
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}

KeySet Inner class ,Hashtable Of Key Of Set aggregate .KeySet Inherited from AbstractSet, therefore ,KeySet There are no duplicate elements in .

 //Hashtable Of Key Of Set aggregate .
//KeySet Inherited from AbstractSet, therefore ,KeySet There are no duplicate elements in .
private class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return getIterator(KEYS);
}
public int size() {
return count;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return Hashtable.this.remove(o) != null;
}
public void clear() {
Hashtable.this.clear();
}
}

entryset Inner class ,Hashtable Of Entry Of Set aggregate .EntrySet Inherited from AbstractSet, therefore ,EntrySet There are no duplicate elements in .

 // Hashtable Of Entry Of Set aggregate .
// EntrySet Inherited from AbstractSet, therefore ,EntrySet There are no duplicate elements in .
private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return getIterator(ENTRIES);
} public boolean add(Map.Entry<K,V> o) {
return super.add(o);
} // lookup EntrySet Include in Object(0)
// First , stay table Find o Corresponding Entry Linked list
// then , lookup Entry Is there... In the list Object
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry entry = (Map.Entry)o;
Object key = entry.getKey();
Entry[] tab = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry e = tab[index]; e != null; e = e.next)
if (e.hash==hash && e.equals(entry))
return true;
return false;
} // Remove elements Object(0)
// First , stay table Find o Corresponding Entry Linked list
// then , Delete the elements in the linked list Object
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
K key = entry.getKey();
Entry[] tab = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry<K,V> e = tab[index], prev = null; e != null;
prev = e, e = e.next) {
if (e.hash==hash && e.equals(entry)) {
modCount++;
if (prev != null)
prev.next = e.next;
else
tab[index] = e.next; count--;
e.value = null;
return true;
}
}
return false;
} public int size() {
return count;
} public void clear() {
Hashtable.this.clear();
}
}

ValueCollection Inner class ,Hashtable Of value Of Collection aggregate .ValueCollection Inherited from AbstractCollection, therefore ,ValueCollection The elements in can be repeated .

// Hashtable Of value Of Collection aggregate .
// ValueCollection Inherited from AbstractCollection, therefore ,ValueCollection The elements in can be repeated .
private class ValueCollection extends AbstractCollection<V> {
public Iterator<V> iterator() {
return getIterator(VALUES);
}
public int size() {
return count;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
Hashtable.this.clear();
}
}

EmptyIterator, Empty the iterator . When Hashtable The actual size of is 0; here , You have to iterate through Hashtable when , The return is “ Empty the iterator ” The object of .

// Empty the iterator 
// When Hashtable The actual size of is 0; here , You have to iterate through Hashtable when , The return is “ Empty the iterator ” The object of .
private static class EmptyIterator implements Iterator<Object> {
EmptyIterator() {
}
public boolean hasNext() {
return false;
}
public Object next() {
throw new NoSuchElementException("Hashtable Iterator");
}
public void remove() {
throw new IllegalStateException("Hashtable Iterator");
}
}

EmptyEnumerator, Empty enumeration class . When Hashtable The actual size of is 0; here , Through again Enumeration Traverse Hashtable when , The return is “ Empty enumeration class ” The object of

// Empty enumeration class 
// When Hashtable The actual size of is 0; here , Through again Enumeration Traverse Hashtable when , The return is “ Empty enumeration class ” The object of .
private static class EmptyEnumerator implements Enumeration<Object> {
EmptyEnumerator() {
}
// Empty enumeration class hasMoreElements() Always return false
public boolean hasMoreElements() {
return false;
} // Empty enumeration class nextElement() Throw an exception
public Object nextElement() {
throw new NoSuchElementException("Hashtable Enumerator");
}
}

Enumerator The purpose of this is to provide " adopt elements() Traverse Hashtable The interface of " and " adopt entrySet() Traverse Hashtable The interface of ".

 //Enumerator The purpose of this is to provide " adopt elements() Traverse Hashtable The interface of " and " adopt entrySet() Traverse Hashtable The interface of ".
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
// Point to Hashtable Of table
Entry[] table = Hashtable.this.table;
//Hashtable The total size of
int index = table.length;
Entry<K,V> entry = null;
Entry<K,V> lastReturned = null;
int type; //Enumerator yes " iterator (Iterator)" still " Enumeration class (Enumeration)" The logo of
//iterator by true, Means it's an iterator ; otherwise , It's an enumeration class .
boolean iterator;
// Will be Enumerator It's used as an iterator , Used to implement fail-fast Mechanism .
protected int expectedModCount = modCount;
Enumerator(int type, boolean iterator) {
this.type = type;
this.iterator = iterator;
}
// From traversal table Look forward to the end of the array of , Until we find something not for null Of Entry.
public boolean hasMoreElements() {
Entry<K,V> e = entry;
int i=index;
Entry[] t=table;
/*Use locals for faster loop iteration */
while (e == null && i > 0) {
e = t[--i];
}
entry = e;
index = i;
return e != null;
} // Get next element
// Be careful : from hasMoreElements() and nextElement() It can be seen that “Hashtable Of elements() Traverse the way ”
// First , Traversal from back to front table Array .table Each node of the array is a one-way list (Entry).
// then , Traverse backward one-way list in turn Entry.
public T nextElement() {
Entry<K,V> et = entry;
int i = index;
Entry[] t = table;
/* Use locals for faster loop iteration */
while (et == null && i > 0) {
et = t[--i];
}
entry = et;
index = i;
if (et != null) {
Entry<K,V> e = lastReturned = entry;
entry = e.next;
return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
}
throw new NoSuchElementException("Hashtable Enumerator");
} // iterator Iterator To determine whether the next element exists
// actually , It's called hasMoreElements()
public boolean hasNext() {
return hasMoreElements();
} // The iterator gets the next element
// actually , It's called nextElement()
public T next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return nextElement();
} // Iterator remove() Interface .
// First , It's in table Array to find the element to be deleted Entry,
// then , Delete one way linked list Entry The elements in .
public void remove() {
if (!iterator)
throw new UnsupportedOperationException();
if (lastReturned == null)
throw new IllegalStateException("Hashtable Enumerator");
if (modCount != expectedModCount)
throw new ConcurrentModificationException(); synchronized(Hashtable.this) {
Entry[] tab = Hashtable.this.table;
int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; for (Entry<K,V> e = tab[index], prev = null; e != null;
prev = e, e = e.next) {
if (e == lastReturned) {
modCount++;
expectedModCount++;
if (prev == null)
tab[index] = e.next;
else
prev.next = e.next;
count--;
lastReturned = null;
return;
}
}
throw new ConcurrentModificationException();
}
}
}

contains() and containsValue() It's all about judgment Hashtable Does it include “ value (value)”

public boolean containsValue(Object value) {
return contains(value);
} public synchronized boolean contains(Object value) {
// Hashtable in “ Key value pair ” Of value It can't be null,
// if null Words , Throw an exception !
if (value == null) {
throw new NullPointerException();
} // Traverse from back to front table Elements in an array (Entry)
// For each Entry( One way linked list ), One by one , Determine whether the value of the node is equal to value
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}

Other methods

public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>,Cloneable,java.io.Serializable {
// Member variables as above
// As above public synchronized int size() {
return count;
} public synchronized boolean isEmpty() {
return count == 0;
}
// return “ all key” Enumeration objects for
public synchronized Enumeration<K> keys() {
return this.<K>getEnumeration(KEYS);
}
// return “ all value” Enumeration objects for
public synchronized Enumeration<V> elements() {
return this.<V>getEnumeration(VALUES);
}
//contains()、containsValue() and containsKey() Above // return key Corresponding value, If not, return to null
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
// Calculate index value
int index = (hash & 0x7FFFFFFF) % tab.length;
// find “key Corresponding Entry( Linked list )”, Then find out in the list “ Hash value ” and “ Key value ” And key All equal elements
for(Entry<K,V> e = tab[index]; e != null ; e = e.next) {
if((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
} //rehash() Above
//put()、clone() Above
//remove() Delete Hashtable The middle key is key The elements of // take “Map(t)” Add all the elements of to one by one Hashtable in
public synchronized void putAll(Map<? extends K, ? extends V> t) {
for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
put(e.getKey(), e.getValue());
} // Empty Hashtable
// take Hashtable Of table The values of the array are all set to null
public synchronized void clear() {
Entry tab[] = table;
modCount++;
for (int index = tab.length; --index >= 0; )
tab[index] = null;
count = 0;
} public synchronized String toString() {
int max = size()- 1;
if (max == -1)
return "{}"; StringBuilder sb = new StringBuilder();
Iterator<Map.Entry<K,V>> it = entrySet().iterator(); sb.append('{');
for (int i = 0; ; i++) {
Map.Entry<K,V> e = it.next();
K key = e.getKey();
V value = e.getValue();
sb.append(key == this ? "(this Map)" : key.toString());
sb.append('=');
sb.append(value == this ? "(this Map)" : value.toString()); if (i == max)
return sb.append('}').toString();
sb.append(", ");
}
} // obtain Hashtable Enumeration class objects of
// if Hashtable The actual size of is 0, Then return to “ Empty enumeration class ” object ;
// otherwise , Return to normal Enumerator The object of .
private <T> Enumeration<T> getEnumeration(int type) {
if (count == 0) {
return (Enumeration<T>)emptyEnumerator;
} else {
return new Enumerator<T>(type, false);
}
} // obtain Hashtable The iterator
// if Hashtable The actual size of is 0, Then return to “ Empty the iterator ” object ;
// otherwise , Return to normal Enumerator The object of .(Enumerator Implemented two interfaces of iterator and enumeration )
private <T> Iterator<T> getIterator(int type) {
if (count == 0) {
return (Iterator<T>) emptyIterator;
} else {
return new Enumerator<T>(type, true);
}
} // Hashtable Of “key Set ”. It's a Set, There are no repeating elements
private transient volatile Set<K> keySet = null;
// Hashtable Of “key-value Set ”. It's a Set, There are no repeating elements
private transient volatile Set<Map.Entry<K,V>> entrySet = null;
// Hashtable Of “key-value Set ”. It's a Collection, Can have repeating elements
private transient volatile Collection<V> values = null; // Return to a synchronizedSet After the encapsulation KeySet object
//synchronizedSet The purpose of encapsulation is to KeySet All methods of add synchronized, Achieve multi thread synchronization
public Set<K> keySet() {
if (keySet == null)
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
} // Return to a synchronizedSet After the encapsulation EntrySet object
//synchronizedSet The purpose of encapsulation is to EntrySet All methods of add synchronized, Achieve multi thread synchronization
public Set<Map.Entry<K,V>> entrySet() {
if (entrySet==null)
entrySet = Collections.synchronizedSet(new EntrySet(), this);
return entrySet;
} // Return to a synchronizedCollection After the encapsulation ValueCollection object
// synchronizedCollection The purpose of encapsulation is to ValueCollection All methods of add synchronized, Achieve multi thread synchronization
public Collection<V> values() {
if (values==null)
values = Collections.synchronizedCollection(new ValueCollection(),this);
return values;
} // again equals() function
// If two Hashtable All of the key-value All key value pairs are equal , Then judge that they are equal
public synchronized boolean equals(Object o) {
if (o == this)
return true; if (!(o instanceof Map))
return false;
Map<K,V> t = (Map<K,V>) o;
if (t.size() != size())
return false; try {
// Take out the current... In turn through the iterator Hashtable Of key-value Key value pair
// And judge the key value to , Exist in Hashtable in .
// If it does not exist , Return immediately false; otherwise , End of traversal “ At present Hashtable” And back to true.
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(t.get(key)==null && t.containsKey(key)))
return false;
} else {
if (!value.equals(t.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
} // Calculation Entry Of hashCode
// if Hashtable The actual size of is 0 perhaps Load factor <0, Then return to 0.
// otherwise , return “Hashtable Each of the Entry Of key and value Exclusive or values The sum of ”.
public synchronized int hashCode() {
int h = 0;
if (count == 0 || loadFactor < 0)
return h; // Returns zero loadFactor = -loadFactor; // Mark hashCode computation in progress
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
for (Entry e = tab[i]; e != null; e = e.next)
h += e.key.hashCode() ^ e.value.hashCode();
loadFactor = -loadFactor; // Mark hashCode computation complete
return h;
} private void reconstitutionPut(Entry[] tab, K key, V value)
throws StreamCorruptedException
{
if (value == null) {
throw new java.io.StreamCorruptedException();
}
// Makes sure the key is not already in the hashtable.
// This should not happen in deserialized version.
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
throw new java.io.StreamCorruptedException();
}
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<K,V>(hash, key, value, e);
count++;
} private static final int KEYS = 0;
private static final int VALUES = 1;
private static final int ENTRIES = 2; private static Enumeration emptyEnumerator = new EmptyEnumerator();
private static Iterator emptyIterator = new EmptyIterator();
}

summary

in the light of Hashtable, We also give some important conclusions , But combine with HashMap To sum up .

  • Both have the same storage structure and conflict resolution .
  • HashTable The default capacity without specifying capacity is 11, and HashMap by 16,Hashtable Don't ask the capacity of the underlying array to be 2 Omega to an integer power , and HashMap The requirement must be 2 Omega to an integer power .
  • Hashtable in key and value no null, and HashMap in key and value All allowed null(key There can only be one for null, and value You can have more than one null). But if Hashtable There is something similar in put(null,null) The operation of , Compilation can also be done through , because key and value All are Object type , But the runtime throws NullPointerException abnormal , This is a JDK According to the rules . Let's see ContainsKey Methods and ContainsValue Source code :
 // Judge Hashtable Does it include “ value (value)”
public synchronized boolean contains(Object value) {
// Be careful ,Hashtable Medium value It can't be null,
// if null Words , Throw an exception !
if (value == null) {
throw new NullPointerException();
} // Traverse from back to front table Elements in an array (Entry)
// For each Entry( One way linked list ), One by one , Determine whether the value of the node is equal to value
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
} public boolean containsValue(Object value) {
return contains(value);
} // Judge Hashtable Does it include key
public synchronized boolean containsKey(Object key) {
Entry tab[] = table;
// Calculation hash value , Direct use key Of hashCode Instead of
int hash = key.hashCode();
// Calculate the index value in the array
int index = (hash & 0x7FFFFFFF) % tab.length;
// find “key Corresponding Entry( Linked list )”, Then find out in the list “ Hash value ” and “ Key value ” And key All equal elements
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}

Obviously , If value by null, Will be thrown directly NullPointerException abnormal , But there's no right in the source code key Is it null Judge , A little puzzled ! however NullPointerException Belong to RuntimeException abnormal , It can be done by JVM Automatically thrown , Maybe right key The value of the JVM There's a limit to it .

  • Hashtable Add capacity , Change the capacity to the original 2 Doubling 1, and HashMap Add capacity , Change the capacity to the original 2 times .
  • Hashtable Calculation hash value , Direct use key Of hashCode(), and HashMap Recalculated key Of hash value ,Hashtable In seeking hash When the position index corresponding to the value , With modular operations , and HashMap When looking for a location index , Use and operate , And here we usually use hash&0x7FFFFFFF after , Right again length modulus , &0x7FFFFFFF The goal is to make negative hash The value is converted to a positive value , because hash Value may be negative , and &0x7FFFFFFF after , Only changes outside the symbol , And the last bits are the same .

JAVA Of HashTable More articles on source code analysis

  1. Java Basics ——HashTable Source code analysis

    HashTable Hash table based Map Interface synchronization implementation HashTable Of the elements of key Is the only one. ,value The value is repeatable HashTable Of the elements of key and value It is not allowed to be null, If you encounter null, Then return ...

  2. java.util.Hashtable Source code analysis

    Hashtable Implement a key value mapping table . Anything that is not null Of object Can be used as key and value. In order to access objects , Objects placed in tables must implement hashCode and equals Method . One Hashtable There are two ...

  3. Java A collection of introductory series Hashtable Source code analysis ( 11、 ... and )

    Preface In the previous section, we implemented hash algorithm and used open address method and chain address method for conflict resolution , In this section, we will analyze the source code in detail , Take a look at which way conflicts are used in the source code and compare what we've implemented , What can be changed . Hash ...

  4. Concurrent -HashMap and HashTable Source code analysis

    HashMap and HashTable Source code analysis Reference resources : https://blog.csdn.net/luanlouis/article/details/41576373 http://www.cnblog ...

  5. The simplest in history HashTable Source code analysis

    HashTable Source code analysis 1. Preface Hashtable An old-fashioned collection class , As early as JDK 1.0 It was born 1.1. Abstract In the first chapter of the collection series , We know that ,Map The implementation classes of are HashMap.Link ...

  6. Java split Method source code analysis

    Java split Method source code analysis public String[] split(CharSequence input [, int limit]) { int index = 0; // The pointer bool ...

  7. 【JAVA】ThreadLocal Source code analysis

    ThreadLocal Inside is a hash table to store : static class ThreadLocalMap { static class Entry extends WeakReference<T ...

  8. 【Java】HashMap Source code analysis —— Detailed explanation of common methods

    In the last introduction HashMap Basic concepts of , This article focuses on HasHMap Some of the common methods in :put()get()**resize()** First introduced resize() This method , In my opinion, this is HashMap One of them is very ...

  9. 【Java】HashMap Source code analysis —— Basic concepts

    stay JDK1.8 after , Yes HashMap The source code has changed , Red black tree introduced . before this ,HashMap It's actually an array + The structure of the list , because HashMap It's a hash table , It creates hash conflicts , To solve the hash conflict ,HashMa ...

Random recommendation

  1. from objC What comes to mind at runtime ...

    objC Languages are not just object-oriented ( encapsulation , Inheritance and polymorphism ), It also has the flexibility of a scripting language ( Runtime ), This makes objC It has a lot of strange functions - You can add methods to a class or object at run time , You can even add class methods , You can even create classes dynamically . ...

  2. MFC About how to browse files

    When making the interface , If it comes to documents , Just enter the address of the file The first method is direct input , Um. ...╮( ̄▽ ̄)╭ The second way is common browsing , Then select the file <( ̄︶ ̄)/ The code is as follows : CString filena ...

  3. linux Show -bash-4.2# problem

    today , After installation and configuration mysql after , Reconnected shell It's not root@localhost # 了 , It shows -bash-4.2# Prompt information : Last login: Tue Apr 5 00:3 ...

  4. React Learning notes ( Two ) Component state

    State of component (this.state): Components must interact with users ,React A big innovation of , Think of components as a state machine , There is an initial state at the beginning , Then the user interacts , Cause state change , This triggers a re rendering UI getIni ...

  5. VIJOS 1512SuperBrother Whac-A-Mole ( A two-dimensional BIT)

    ha-ha .. Two dimensional tree array , The second and first dimensions are basically the same . --------------------------------------------------------------------------- ...

  6. Linux Shell Script introduction

    -Linux Shell Script introduction In conclusion , This book is very practical and practical , All of them are concrete examples , It can be operated directly on the terminal , It's much more practical than just looking at it , The other is , This book also covers a wide range of contents , From text manipulation to server management ...

  7. Activate JetBrains PhpStorm 2016.3.2 and JetBrains WebStorm 2016.3.2

    1. open phpstorm 2. In the activation screen, select license server Online activation mode Input :http://idea.imsxm.com/ 3. Activation successful , Open the use

  8. beagleboneblack HDMI Can't show

    beagleboneblack   Connect HDMI On TV , No display After reading the information, I know http://elinux.org/Beagleboard:BeagleBoneBlack_HDMI#Conn ...

  9. huffman Compress and unzip files 【 Code 】

    It's been a week since I wrote Huffman code last time , I've been writing all week huffman Compression decompression , Ah , Waste a lot of time on a lot of small mistakes bug. In fact, the most important part of this program is not what I think , It's a reference to a friend's code , however , in any case , since ...

  10. The first morning ——HTML Basic knowledge of web pages and related content

    I learned this morning HTML Basic knowledge and related content , also DW The basic use method . HTML(HyperText Markup Language): Hypertext markup language , Hypertext : In addition to the text in the web page , It also includes pictures , ...