Data Structures in Python compared with Java: HashMap, collision resolution

Here comes my favorite data structure in Java, the HashMap. In Python, a similar implementation is called Dictionary. Both uses hash table implementation. I don't want to go through the concept of hash table, but feel free to Wiki it.

The main difference between Java's HashMap and Python's dictionary is the collision resolution. In short, when you insert a key-value pair into the table, a hash function will "transfer" the key to a hash value which will then be mod by the length of the table and get the position of the table to insert this key-value pair. However, in some cases, especially when your hash function is NOT A GOOD ONE, multiple keys will be hashed to the same spot. So the question is, how to solve this problem?

First of all, is to write a good hash function. Now consider you are not a super genius mathematician, you want to find other ways to make up for it. And here comes the collision resolution.

Java
In Java, the HashMap implementation uses what is called separate chaining. The hash table itself is an array of linked list. When multiple keys are hashed to the same slot, they are appended to their predecessor. See the code snippet from JDK 7 implementation.

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

Now here comes the searching problem, what if all keys are hashed to the same slot? Then we will have the worst case, linear search time. However, it is shown that when the load factor is less than 2, the average searching time is O(1)[1]. In Java, the load factor is 0.75, so, not too bad.

Ok, definition:
load factor = number of key-value pairs in the table / capacity of the table

If you are interested where the above code comes from and how Java implements HashMap, see here.


Python
Python developers decided to use another method: double hashing. This is a probing method. When collision occurs, we need to probe and find another empty slot for the key-value pair. There are several different ways of probing, including linear probing, quadratic probing and double hashing. In double hashing, when collision occurs, the key is hashed by a second hashing function and the result is used as a constant factor to find another slot:

slot = (hash1(key) + i * hash2(key)) % length(table)

i indicates the i-th probe. For example, if 'a' is hashed to slot 1 and it is occupied, and hash2('a') = 37, then slot = (1 + 1 * 37) % length(table). Assuming this time it's 3, but 3 is also occupied, then i = 2, and we calculate another slot.

The advantage of double hashing is that multiple keys that are hashed to the same slot will not have the same probing sequence, thus reduces what is called "clustering" problem. In short, the chance of each slot get selected is more uniformly distributed across the table compare to linear and quadratic probing.

However, this means hash1 should not equal hash2. It is shown that when load factor is between 1/2 to 2/3, using double hash allows hashing operations to be on average O(1)[1].

I don't have the CPhython dict implementation here, but I have my own code. ;D

import math

UNUSED = None
DEFAULT_INITIAL_CAPACITY = 1 << 4  # initial size of the table


class HashMap:

    loadFactor = 2/3

    def __init__(self, capacity=DEFAULT_INITIAL_CAPACITY, load_factor=loadFactor):
        self._table = [None] * capacity
        self._size = 0
        self.loadFactor = load_factor
        self._threshold = math.ceil(len(self._table) * load_factor)

    def __len__(self):
        """
        return the size of the hashmap
        :return:
        """
        return self._size

    def __contains__(self, key):
        """
        if the hashmap contains a given key
        :param key:
        :return:True if contains the value
        """

        return self._findSlot(key, True) is not None

    def add(self, key, value):
        """
        add a key-value pair, if the key already exists, update the value
        :param key:
        :param value:
        :return:
        """
        if key in self:
            slot = self._findSlot(key, True)
            self._table[slot] = _MapEntry(key, value)
            return False
        else:
            slot = self._findSlot(key, False)
            self._table[slot] = _MapEntry(key, value)
            self._size += 1
            if self._size >= self._threshold:
                self._resize()
            return True

    def valueOf(self, key):
        """
        given a key, return the value if the key exists in the table
        :param key:
        :return:
        """
        slot = self._findSlot(key, True)
        assert slot is not None, "Map does not contain such key."
        return self._table[slot].value


    def remove(self, key):
        """
        given a key, remove the key-value pair if the key exists in the table
        :param key:
        :return:
        """
        slot = self._findSlot(key, False)
        assert slot is not None, "Map does not contain such key."
        entry = self._table[slot]
        self._table.remove(entry)
        return entry.value

    def __iter__(self):
        return self

    def _findSlot(self, key, exist):
        """
        Given a key, find a spot in the table
        :param key:
        :param exist:boolean value indicates if the given key is assumed
        to be in the table or not
        :return:if exist, return the slot where the key-value pair is stored if
        the key exists in the table, otherwise return None
        if not exist, return an unused slot
        """
        slot = self._hash1(key)
        step = self._hash2(key)

        M = len(self._table)
        while self._table[slot] is not UNUSED:
            if exist and \
                    (self._table[slot].key == key):
                return slot
            else:
                slot = (slot + step) % M
        if not exist:
            return slot

    def _resize(self):
        """
        resize the table when the size reaches threshold
        :return:
        """
        origTable = self._table
        newSize = len(self._table) * 2 + 1
        self._table = [None] * newSize

        self._size = 0
        self._threshold = math.ceil(len(self._table) * self.loadFactor)

        for entry in origTable:
            if entry is not UNUSED:
                slot = self._findSlot(entry.key, False)
                self._table[slot] = entry
                self._size += 1

    def _hash1(self, key):
        """
        main hash for mapping keys to the table
        :param key:
        :return:
        """
        return abs(hash(key)) % len(self._table)

    def _hash2(self, key):
        """
        second hash for double hashing probes
        :param key:
        :return:
        """
        return 1 + abs(hash(key)) % (len(self._table) - 2)


class _MapEntry:

    def __init__(self, key, value):
        self.key = key
        self.value = value

Reference:
[1] Rance D. Necaise, "Data Structures and Algorithms Using Python". Wiley, 2010.



*********************************************************************

"I'm no fool, no, I'm not a follower

I don't take things as they come, if they bring me down

Life can be cruel, if you're a dreamer

I just wanna have some fun, don't tell me what can't be done

You know you like it but it drives you insane

You know you like it but it drives you insane

You know you like it but you're scared of the shame

What you want, what you gonna do?

You know you like it but it drives you insane

Follow me 'cause you know that you wanna feel the same

You know you like it but it drives you insane

What you want, what you gonna do?"

Assign numbers

There are numbers in between 0-9999999999 (10-digits) which are assigned to someone.

Write two methods called "getNumber" and "requestNumber" as follows: 

Number getNumber();

boolean requestNumber(Number number);

getNumber method should find out a number that did not assigned than marks it as assigned and return that number.

requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assigned and return true.

Design a data structure to keep those numbers and implement those methods

I like this problem a lot because it tests you two things: how to handle large data that may not fit into memory and how to use bits. I am good at neither. :(

Well, first, memory. So we have 10^10 numbers, each number takes 4 byte, so in total we will have ...eh... 40 GB data (thank you, Google!). It definitely cannot fit into the memory, so how should we deal with it? Remember 4 byte = 32 bits, so 1 integer takes 32 bits, can we only use 1 bit? That can reduce the memory to 40 / 32 ~ 1.25 GB, if we have a machine with 2 GB memory, we can handle it!

Yup, here comes the second, the BitSet. I wasn't quite familiar with the concept. A bit set is a vector of bits that grows as needed.  Each component of the bit set has a boolean value. So consider if I initialize a BitSet with initial size of 32, by flipping each component in the set (true -> false or false -> true), we can get 2^32 numbers, and that fits our problem set.

For the requestNumber() part, I use a hashSet to store all added numbers, this will allow retrieval of the number takes only O(1) time.

/**
 * 
 *There are numbers in between 0-9999999999 (10-digits) which are 
 *assigned to someone (does not matter which number assigned to whom) 
 *Write two methods called "getNumber" and "requestNumber" as follows 
 *
 *Number getNumber(); 
 *boolean requestNumber(Number number); 
 *
 *getNumber method should find out a number that 
 *did not assigned than marks it as assigned and return that number. 
 *requestNumber method checks the number is assigned or not. 
 *If it is assigned returns false, else marks it 
 *as assigned and return true. 
 *design a data structure to keep those numbers and implement those methods
 * @author shirleyyoung
 *
 */
import java.util.*;
public class AssignNumbers {
 private static BitSet bits = new BitSet(32);
 private static Set numbers = new HashSet ();
 private static void toBitSet(int number) {
  int index = 0;
  while (number != 0) {
   if (number % 2 != 0)
    bits.set(index);
   index++;
   // >> signed
   // >>> unsigned
   number = number >> 1;
  }
 }
 
 private static int toInteger() {
  int value = 0;
  for (int i = 0; i < bits.length();i++) {
   value += bits.get(i) ? (1 << i) : 0;
  }
  return value;
 }
 
 public static int getNumber() {
  if (!numbers.contains(toInteger())) {
   numbers.add(toInteger());
   return toInteger();
  }
  else {
   for (int i = 0; i < 32; i++) {
    bits.flip(i);
    if (!numbers.contains(toInteger())) {
     numbers.add(toInteger());
     return toInteger();
    }
   }
  }
  return -1;
 }
 public static boolean requestNumber(int number) {
  if (numbers.contains(number))
   return false;
  else {
   numbers.add(number);
   toBitSet(number);
   return true;
  }
 }

 public static void main(String[] args) {
  System.out.println(getNumber());
  //System.out.println(requestNumber(123));
  //System.out.println(requestNumber(123));
  //System.out.println(getNumber());
  for (int i = 0; i < 1000; i++) {
   System.out.println(getNumber());
  }

 }
}

Hash table Java implementation

I remember one company has an interview question about implementing a hash table. I couldn't find a good one online (except the Java src, obviously), so I decide to write my own.

However, if you are really interested in how Java implements the Hashtable, go to this website. My friend made this, and I only realized today that it is the best website if you are interested in any source code.

The Entry class
I refer to the Java Hashtable Entry class. There are two key objects in the class: the key, and the value (well, it's map...). It is a private inner class because I don't need to access the Entry class outside the Hashtable class. It is basically a Java Bean which contains two constructors, an object representing the key and an object representing the value of the data.

The hash method
Java uses hashCode() method. I referred to this blog, which uses Java's toString() method.

Separating chaining
I use LinkedList implementation. I still keep the load factor and resize() method presented in Java, just for learning purpose. However, I would strongly recommend you only preserve one. The LinkedList implementation is definitely more straightforward, since it doesn't require the copy of the table. However, use a constant size table means the search of the element will take longer time (O(n) if your hash function is not a good one).

The code

import java.util.LinkedList;


public class HashTable {
 private int table_size;
 private Object[] table;
 //coefficient of map usage
 //Actually, I use linkedlist for separate chaining, 
 //thus I don't really have to resize the table,  
 //but for the learning purpose, let's keep it here
 private float loadFactor = 0.75f;
 private int numElements; 
 
 
 public HashTable() {
  this.table_size = 11;
  table = new Object[this.table_size];
 }
 public HashTable(int table_size) {
  if (table_size <= 0)
   throw new IllegalArgumentException("Illegal Capacity" + table_size);
  this.table_size = table_size;
  table = new Object[this.table_size];
 }
 public int size() {
  return this.numElements;
 }
 public boolean isEmpty() {
  return this.numElements == 0;
 }
 
 @SuppressWarnings("unchecked")
 public boolean containsKey(Object key) {
  boolean result = false;
  int hash = this.hash(key);
  if (this.table[hash] != null) {
   Entry node = new Entry();
   node.setKey(key);
   if (((LinkedList)this.table[hash]).indexOf(node) > -1) {
    result = true;
   }
  }
  return result;
 }
 //since we are doing resize, let's keep an eye on the maximum size too
 private static final int MAX_table_size = Integer.MAX_VALUE - 8;
 private void resize()
 {
  int oldSize = table_size;
  if (oldSize == MAX_table_size)
    return;
  // use the java method
  int newSize = (oldSize << 1) + 1;
  if (newSize >= MAX_table_size) {
   newSize = MAX_table_size;
  }
    
  Object[] newTable = new Object[newSize];
  for (int i=0; i)this.table[position]).add(node);
   this.numElements++;
  }
  
  else
  {
   int index = ((LinkedList)this.table[position]).indexOf(node);
   //append the element to the linkedlist
   if (index == -1) {
    ((LinkedList)this.table[position]).add(node);
    this.numElements++;
   }
   //find the node in the linkedList, 
   //set the value
   else {
    ((LinkedList)this.table[position]).get(index).setValue(node.value);
   }
  }
 }
 
 //Get values
 @SuppressWarnings("unchecked")
 public Object get(Object key)
 {
  int hasVal = this.hash(key);
  if (this.table[hasVal] == null)
   throw new Error("no such key!");
  
  Entry node = new Entry();
  node.setKey(key);
  int index = ((LinkedList)this.table[hasVal]).indexOf(node);
  return ((LinkedList)this.table[hasVal]).get(index).getValue();
  
 }
 
 //remove  pairs
 @SuppressWarnings("unchecked")
 public void remove (Object key) {
  int hashVal = this.hash(key);
  if (this.table[hashVal] != null) {
   Entry node = new Entry();
   node.setKey(key);
   if (((LinkedList)this.table[hashVal]).indexOf(node) > -1)  {
          ((LinkedList)this.table[hashVal]).remove(node);
          this.numElements--;
   }
  }
 }
 public void clear() {
  for (int index = this.table.length; --index >= 0;) {
   this.table[index] = null;
  }
  numElements = 0;
 }
 
 @SuppressWarnings("unchecked")
 public String toString() {
  StringBuffer sb = new StringBuffer();
  sb.append(System.getProperty("line.separator"));
  sb.append("{");
  sb.append(System.getProperty("line.separator"));
  for (int i = 0; i < this.table.length; i++) {
   if (this.table[i] != null) {
    //"\t" tab
    sb.append("  " + (LinkedList) this.table[i]);
    sb.append(System.getProperty("line.separator"));
   }
  }
  sb.append("}");
  return sb.toString();
 }

 private int hash(Object key) {
  //Start with a base, just so that it's not 0 for empty strings
     int result = 27;
     
     String inputString = key.toString().toLowerCase();
     
     char[] characters = inputString.toCharArray();
     for (int i = 0; i < characters.length; i++)
     {
      char currentChar = characters[i];
      if (currentChar == 'a' || currentChar == 'b' || currentChar == 'c' ||
          currentChar == 'e' || currentChar == 'e' || currentChar == 'f')
       result += Integer.parseInt("" + currentChar,16);//convert to hexidecimal
      int j = (int)currentChar;
      result += j;
     }
     result ^= (result >>> 20) ^ (result >>> 12);
     return result % this.table_size;  
 }
 //I maintained the Entry name, 
 //but since it's a simplified implementation
 //I am not going to implement Map.Entry
 //http://www.codatlas.com/project/L_fXVCOhW4_lzXEd3R5DNQ__/src/share/classes/java/util/Hashtable.java?keyword=hashtable&line=951
 private static class Entry
 {
  private Object key;
  private Object value;
  protected Entry() {
   this.key = null;
   this.value = null;
  }
  protected Entry(Object key, Object value) {
   this.key = key;
   this.value = value;
  }
   
  public Object getKey() {
   return key;
  }
  public Object getValue() {
   return value;
  }
  public void setValue(Object value) {
   if (value == null)
    throw new NullPointerException();
   this.value = value;
  }
  public void setKey(Object key) {
   if (key == null)
    throw new NullPointerException();
   this.key = key;
  }
  public boolean equals(Object obj) {
   //The instanceof keyword can be used to test 
   //if an object is of a specified type.
   if (!(obj instanceof Entry))
    return false;
   Entry node = (Entry)obj;
   //only based on the key alone assuming there can't be 
   //two entries with the same key in the table
   return (this.key == null ? node.getKey() == null : key.equals(node.getKey())); 
  }
  
  public String toString() {
   return this.key.toString() + " has value " + this.value.toString();
  }
 }
 
}

*********************************************************************************
Some notes when I try to understand the Java Hashtable src:
Serialization: the process of making the object's state is persistent. That means the state of the object is converted into stream of bytes and stored in a file.
De-serilization: bring the object's state from bytes.

Transient: the variable should not be serialized. It the variable is declared as transient, then it will not be persisted.
http://www.javabeat.net/what-is-transient-keyword-in-java/

Native: It marks a method, that it will be implemented in other languages, not in Java. It works together with JNI (Java Native Interface).

Native methods were used in the past to write performance critical sections but with Java getting faster this is now less common. Native methods are currently needed when

• You need to call a library from Java that is written in other language.
• You need to access system or hardware resources that are only reachable from the other language (typically C). Actually, many system functions that interact with real computer (disk and network IO, for instance) can only do this because they call native code.