# WEEK 7
## 7.1
### 1. Get method

// Return value v associated with key k, or null
  public V get(K k) {
    final int h = getHash(k), stripe = h % lockCount;
    synchronized(locks[stripe]){
      final int hash = h % buckets.length;

      ItemNode<K,V> node = ItemNode.search(buckets[hash], k);
      return node == null ? null : node.v;
    }
  }

### 2. Size method

public int size() {
    int sum = 0;
    
    for(int stripe = 0; stripe < lockCount; stripe++){
      synchronized(locks[stripe]){
        sum += this.sizes[stripe];
      }
    }
    
    return sum;
  }

_Explain why it is important to lock stripe s when reading its size from sizes[s] :_
- Because an other thread could be doing actions that could impact size in the mean time
### 3 & 4. Put if absent + reallocation method

// Put v at key k only if absent
  public V putIfAbsent(K k, V v) {
    final int h = getHash(k), stripe = h % lockCount;
    synchronized(locks[stripe]){
      if(containsKey(k))
        return get(k);
      else{
        final int hash = h % buckets.length;
        buckets[hash] = new ItemNode<K,V>(k, v, buckets[hash]);
        sizes[stripe]++;
        
        if(sizes[stripe]>(buckets.length/lockCount))
          reallocateBuckets();
        
        return null;
      }
    }
  }

### 5. Put if absent method

  // Remove and return the value at key k if any, else return null
  public V remove(K k) {
    final int h = getHash(k), stripe = h % lockCount;

    synchronized(locks[stripe]){
      
      final int hash = h % buckets.length;
      ItemNode<K,V> prev = buckets[hash];
      // No element in the map
      if(prev == null)
        return null;
      // If the given element is the head of map
      else if(k.equals(prev.k)){
        V old = prev.v;
        this.sizes[stripe]--;
        buckets[hash] = prev.next;
        return old;
      }else{
        while (prev.next != null && !k.equals(prev.next.k))
          prev = prev.next;
        if (prev.next != null) {  // Delete ItemNode prev.next
          V old = prev.next.v;
          this.sizes[stripe]--;
          prev.next = prev.next.next;
          return old;
        } else
          return null;
      }
    }
  }

### 6. For each method

public void forEach(Consumer<K,V> consumer) {

     for (int hash=0; hash<buckets.length; hash++) {
      ItemNode<K,V> node = buckets[hash];
      if(node != null){
      final int h  = getHash(node.k);
      final int stripe =  h % lockCount;
      synchronized(locks[stripe]){

        while (node != null) {
        consumer.accept(node.k, node.v);
        node = node.next;
        }  
      }  
     }
    }
  }

We choose to implement method (1) because ...

### 7 and 8 Test and time measurement

# OS:   Mac OS X; 10.14.6; x86_64
# JVM:  Oracle Corporation; 12.0.1
# CPU:  null; 4 "cores"
# Date: 2019-10-10T10:59:51+0200

class SynchronizedMap
        17 maps to B
       117 maps to C
        34 maps to F
       217 maps to E
        17 maps to B
        17 maps to B
       217 maps to E
        34 maps to F
       217 maps to E
        17 maps to B
        34 maps to F

class StripedMap
        17 maps to B
       117 maps to C
        34 maps to F
       217 maps to E
        17 maps to B
        17 maps to B
       217 maps to E
        34 maps to F
       217 maps to E
        17 maps to B
        34 maps to F

class WrapConcurrentHashMap
        17 maps to B
       117 maps to C
        17 maps to B
        34 maps to F
       217 maps to E
        17 maps to B
        34 maps to F
       217 maps to E
        17 maps to B
        34 maps to F
       217 maps to E

SynchronizedMap       16         624550,0 us   26337,13          2
99992.0

StripedMap            16         278238,9 us   88527,71          2
99992.0

WrapConcHashMap       16         270839,5 us  138947,41          2
99992.0

The gap between SynchronizedMap (624550,0 us) and StripedMap (278238,9 us) is as expected, since multiple thread can update the map at the same time (unlike SynchronizedMap)

### 9

It may be because having a single thread working on each strip would cause a lot of overhead

### 10
Having 32 threads improve the probability of not having to wait on a lock

### 11
It can be problematic with regards to thread safety because we can risk that one of the threads locks the stripe while the other intervening thread calls reallocateBuckets.

## 7.2
### 1. Get

// Return value v associated with key k, or null
  public V get(K k) {
    final ItemNode<K,V>[] bs = buckets;
    final int h = getHash(k), stripe = h % lockCount, hash = h % bs.length;
    
    // The sizes access is necessary for visibility of bs elements
    if(sizes.get(stripe) != 0){
      if(ItemNode.search(bs[hash], k, null)){
        return bs[hash].v;
      }else
       return null;

    }else
    return  null;
  }

### 2. Size

public int size() {
     int sum = 0;
    
    for(int stripe = 0; stripe < lockCount; stripe++)
        sum += sizes.get(stripe);
    return sum;
  }

### 3. putIfAbsent

 // Put v at key k only if absent.  
  public V putIfAbsent(K k, V v) {
    final int h = getHash(k), stripe = h % lockCount;
    final Holder<V> old = new Holder<V>();
    ItemNode<K,V>[] bs;
    int afterSize; 
    synchronized (locks[stripe]) {
      if(containsKey(k))
        return get(k);

      bs = buckets;
      final int hash = h % bs.length;
      final ItemNode<K,V> node = bs[hash], 
      newNode = ItemNode.delete(node, k, old);
      bs[hash] = new ItemNode<K,V>(k, v, newNode);
      // Write for visibility; increment if k was not already in map
      afterSize = sizes.addAndGet(stripe, newNode == node ? 1 : 0);
    }
    if (afterSize * lockCount > bs.length)
      reallocateBuckets(bs);
    return null;
  }

Why do you not need to write to the stripe size if nothing was added?

Because the size hasn't changed

### 4. Remove

 // Remove and return the value at key k if any, else return null
  public V remove(K k) {
    final int h = getHash(k), stripe = h % lockCount;
    ItemNode<K,V>[] bs = buckets;
    
    final ItemNode<K,V> node = bs[h % bs.length];
    final Holder<V> old = new Holder<V>();
    
    synchronized(locks[stripe]){
      ItemNode.delete(node,k,old);
      if(old.get() != null)
        sizes.addAndGet(stripe, -1);
    }
    return old.get();
    
  }

### 5. For each

// Iterate over the hashmap's entries one stripe at a time.  
  public void forEach(Consumer<K,V> consumer) {
    ItemNode<K,V>[] bs = buckets;
    for (int stripe=0; stripe<bs.length; stripe++) {
      ItemNode<K,V> node = bs[stripe];
        while (node != null) {
          consumer.accept(node.k, node.v);
          node = node.next;
      }  
    }
  }

### 6

# OS:   Mac OS X; 10.14.6; x86_64
# JVM:  Oracle Corporation; 12.0.1
# CPU:  null; 4 "cores"
# Date: 2019-10-21T13:59:14+0200
SynchronizedMap       16         651667,6 us   21744,63          2
99992.0
StripedMap            16         271182,7 us   92589,24          2
99992.0
StripedWriteMap       16         234427,6 us  136565,79          2
71271.15
WrapConcHashMap       16         232737,3 us  130171,54          2
99992.0

Our StripedWriteMap seems to be faster (as expected) than our StripedMap. It makes sense because we only lock on write and not on read