ConcurrentHashMap Implementation

I have written a simplified version of my own MyConcurrentHashMap. I tried to make use of a Lock[] array for Lock striping, so that all put() operations to the MyConcurrentHashMap is through a lock if required. Also, I made my own MyHashMap made internally as the backing data structure for MyConcurrentHashMap. I created it my own as I wanted to qualify the value field as volatile for volatile read operation without an explicit locking. This ensures that the get() operation is a non synchronized call with implicit locking at memory level though volatile read and not via acquiring a lock anytime which makes it lighter. Have a look and provide your inputs and improvements if any:

```
import java.util.LinkedList;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class MyConcurrentHashmap {

private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

private static final int INITIAL_CAPACITY = 16;

private float LOAD_FACTOR = 0.75f;

private int capacity = INITIAL_CAPACITY;

private int size;

private Lock[] locks;

private MyHashMap myHashMap = new MyHashMap();

private class MyHashMap {
private LinkedList[] lists = new LinkedList[INITIAL_CAPACITY];

private class MapEntry {
final Object key;
volatile Object value;

MapEntry(Object key, Object value) {
this.key = key;
this.value = value;
}
}

void put(Object key, Object value) {
if (key == null)
throw new IllegalArgumentException("Key Cannot be Null");
int hash = key.hashCode();
hash %= lists.length;
if (size >= LOAD_FACTOR * lists.length) {
capacity = lists.length * 2;
LinkedList[] tempLists = new LinkedList[capacity];
System.arraycopy(lists, 0, tempLists, 0, lists.length);
lists = tempLists

This is a pretty complicated task and I'd bet there'll be problems.

With volatile Object value you assure visibility of value, but Object key gets read before it and it's not final. So there are good chances, it'll break.

if (capacity == LOAD_FACTOR * lists.length) {

With floating-point multiplication, this may never happen. With your LOAD_FACTOR = 0.75f, it may as 0.75 can be represented exactly, but e.g., with 0.4 it'll fail. The test should be =, no idea which one is right.

Possibly none, as you're testing capacity, which never changes. It should be size >= LOAD_FACTOR * lists.length.

The correctness of your get depends on the internal working of the LinkedList.

for (; i < lists[hash].size(); i++) {
        if (((MapEntry) (lists[hash].get(i))) != null
                && ((MapEntry) (lists[hash].get(i))).key.equals(key)) {
            ((MapEntry) (lists[hash].get(i))).value = value;
            break;
        }

As LinkedList has an inefficient get, this is doubly inefficient. Actually triply as you're using it twice. You should iterate the list instead.

Do you put any nulls in the list? If no, then you don't need to test for them.

Use a local variable for lists[hash] and also for the i-th element.

Don't break when you can return and save yourself the test in

if (i == lists[hash].size()) {
        lists[hash].addLast(new MapEntry(key, value));
    }

hash %= lists.length;

As your list.length is always a power of two, you can this much faster hack:

hash &= lists.length - 1;

public Object get(Object key) {
    Integer hash = key.hashCode();
    hash %= myHashMap.capacity();
    return myHashMap.get(key);
  }

Why Integer? Why hash at all when you don't use it?

StackExchange Code Review Q#96686, answer score: 5