cs106 bittiger lesson1

cs bittiger

Arraylist

ArraytList<Integer> a = new ArrayList<>();
a.add(1);
for (int i = 2; i <= 10; i++) {
  a.add(i);
}
a.add(11);

ArrayList的后台是Array
size:1
elementData.length:10;

size:10
elementData.length:10

newCapacity = 10 + 10>>1 = 15

size：11
elementData.length：15

ArrayList: resize

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + oldCapacity >>1;

右移一位操作 >> 相当于除以二
右移比除以二在底层速度快；
oldCapacity = 10;
newCapacity = 10 + 10/2 = 15;

Right shift

eg: binary search

while (low <= high) {
  int mid = (low + high) >>> 1;
  int midVal = a[mid];
  if (midVal < key)
    low = mid + 1;
    else if (midVal > key)
      high = mid - 1;
    else
      return mid; // key found
}

>>>意思是右移 用零补足；
>>意思是右移，用上一个数字补足；

Q： 上面源码binary search那里为什么不考虑溢出？

记住：ArrayList每次resize是1.5倍，然后把所有旧元素的都复制到新的更大后的Array空间里面

ArrayList添加一个新的元素，time complexity是Amortized O(1).

接上面

a.remove(3);

删掉某个元素后，ArrayList把所有被删元素右边的元素都copy到前面一格，再删除掉最后一个重复的元素。

ArrayList

• Resizable Array.
• Access: o(1)
• AddFirst: o(n)
• AddLast: o(1) Amortized (因为涉及到resize)
• RemoveFirst(in general): o(n) （因为要把后面的元素全部copy前一位）
• RemoveLast: o(1)
• Set:o(1) (与access一样）

ArrayDeque

循环队列

ArrayDeque<Integer> a = new ArrayDeque<>();

tail: 0
head: 0
elementData.length: 16 (初始长度16，每次resize是double增长）

• index = (index + 1) % length (index 向右移到底回到左边）
• index = (index - 1 + length) % length(index 向左右移到底回到右边）

位操作： （Note: length = $2^n$)
- index = (index + 1) & (length - 1) index 向右移
- index =（index — 1） &（length - 1）index 向左移

位操作日常生活用的不多，但是用作优化很不错。

编码方式：2's complement 二补码

-1 ： 1111.....1111 （在java里是32个1）

Q： java的编译器会不会把模运算优化成位运算？

Modular Operation

-5 % 3 = ?

Remainder Modular

-5/3 = roundFloor(-1.66)= -2
-2 * 3 = -6
-5 -(-6) = 1

java里的模运算
Math.floorMod(-5,3) = 1

-1 mod 16 = 15

Math.floorMod(-1,16) = 15

Modular Operation Optimization

X mod $2^n$ = X & ($2^n$ - 1)

x mod $10^3$ 95185
mod 1000
185
x mod $2^3$ 11101
mod 1000
101 （直接是后三位）
(二进制） 没看懂这儿怎么算的

ArrayDeque:

• Resizable circular queue
• Access:O(1)但不能从中间access某个元素
• AddFirst:O(1) Amortized(涉及到resize，每次resize都是O（n））
• AddLast:O(1) Amortized(涉及到resize，每次resize都是O（n））
• RemoveFirst:O(1)
• RemoveLast(1)
  -Set:O(1) 但不能从中间access某个元素

eg: 想要找第十个元素，ArrayList和ArrayDeque谁更快？
ArrayList更快
ArrayList: index[9]
ArrayDeque:从head到tail查找

ArrayList是不会被缩短的

LinkedList

public class LinkedList<E> extends... {
  Node<E> first;
  Node<E> last;
}
private static class Node<E> {
  E item;
  Node<E> next;
  Node<E> prev;
  Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
  }
}

Nested class: Node

Why static

在static修饰的那个小类里面，不能访问大类里面的variables. 在大类里面是可以访问小类里面的variables的。比如LinkedList可以访问Node里的next, prev, 但Node里面访问不到Node外面、LinkedList大类里的变量。

Space

100 Data points in LinkedList:
(8 bytes + 8 bytes + 8 bytes) *100 = 2400 bytes

100 Data points in ArrayList:
8 bytes * 100 * 1.5 = 1200 bytes

LinkedList
- Dynamic data structure
- Access: O(n)
- AddFirst:O(1)
- AddLast:O(1)
- RemoveFirst:O(1)
- RemoveLast:O(1)
- Set: O(n)
在java里面，一定是doubly-LinkedList

Interface

Queue<Integer> queue = new ArrayDeque<Integer>();
Queue<Integer> queue = new ArrayDeque<Integer>(1000);
下面这个效率高，初始化一个1000的空间,少了很多次resize.

List<Integer> list = new ArrayList<Integer>(1000);
Deque<Integer> stack = new ArrayDeque<Integer>(1000);

Stack<Integer> stack = new Stack<Integer>();

Hash

Hashing:
Build Index

Object > Number(hash code)
比如查字典时，Object是汉字，hash code是拼音（一种索引）。

Hash Table
- Searchng an element in an array needs _ time complexity.
- Usorted array: O(n)
- Sorted array: O(log n )
- What if we want to build an array-based data structure with
-- Near o(1) search time complesity
-- Near O(1) to add a new element
-- So we can use hashcode to build index

Mapping: hashcode > arrayIndex
arrayIndex = hashCode % length

collision > linear probing
Rehashing

Separate Chain

Hash Table

• Use hashcode and array length to get index of array
• Collision
• • Linear Probing(Clustering) (快一些）
• • Separate Chain
• Rehashing when number of elements is growing faster
• Hash Table
• • Near O(1) search time complexity
• • Near O(1) to add a new element

HashMap

public class More ...HashMap<K,V>
     extends AbstractMap<K,V>
     implements Map<K,V>, Cloneable, Serializable
    {
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    final float loadFactor;
    static final Entry<?,?>[] EMPTY_table = { };
    transient Entry<K,V> [] table = (Entry<K,V> [] ) EMPTY_TABLE;
    }

static class More ...Entry<K,V> implements Map.Entry<K,V> {
         final K key;
         V value;
         Entry<K,V> next;
         final int hash;
 /**
  *  Creates new entry.
  * /
  Entry(int h, K k, V v, Entry<K,V> n) {
             value = v;
             next = n;
             key = k;
             hash = h;     
  }
}

Question:Separate chain?Linear probing?

public V More ...put(K key, V value) {
  if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> 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;
    }

Returns index for hash code h.
    static int More ...indexFor(int h, int length) {
         //assert Integer.btCount(length)==1;
         //"length must be a non-zero power of 2"
         return h & (length-1);
    }

Optimized Modular Formula
X mod $2^n$ = X & ($2^n$ - 1)

HashMap: Iteration:

HashMap(prior to Java7)

• Separate Chain HashTable Implementation
• Default value
  
  • Length: 1<<4(aka 16)
  • Load factor:0.75f
  • IndexFor: hash %length >> hash&(length - 1)

• In Java8, HashMap has some performance improvement

  HashSet is a wrapper class of HashMap, Value is a constant dummy object.

HashSet

 public More ...HashSet() {
        map = new HashMap<E,Object>();
 }
 public boolean More ...add(E e) {
        return map.put(e, PRESENT)==null;
 }
 private static final Object PRESENT = new Object();

Linkedhashmap

linkedList + Hashmap
LinkedList maintain entries in Insert Order.

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
  static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V vaule, Node<K,V> next） {
         super(hash, key, value, next);
    }
  }
  transient LinkedHashMap.Entry<K,V> head;
  transient LinkedHashMap.Entry<K,V> tail;
 }

 void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }