【0231-Week02】递归以及HashMap总结

[sunhongyue4500]

递归的理解

递归最常见的应用是在数学和计算机科学中，在计算机科学中，程序调用自身的编程技巧就是递归。

当递归没有终止条件时，就是无限递归，在盗梦空间中，一个满是镜子的走廊里，镜子反射出无限递归。而在实际的应用中，递归一般都是有终止条件的，无限递归下去，计算机也会stack overflow。

递归的算法模版

普通递归

func recursion(level int, p1 param1, p2 param2) {
  // terminator
  if level >= maxLevel {
    return
  }
  // process 
  process(level)
  // drill down
  recursion(level+1, p1, p2)
  // clear status
  reverseState(level)
}

递归分治，divide & conquer

def divide_conquer(problem, param1, param2, ...) 
	 # recursion terninator
   if problem is None
    	print_result
      return
    
    # prepare data
    data = prepare_data(problem)
    subproblems = split_problems(problem, data)
    
    # conquer subproblems
    subresult1 = self.divide_conque(subproblems[0], p1, ...)
    subresult2 = self.divide_conque(subproblems[1], p1, ...)
    subresult1 = self.divide_conque(subproblems[2], p1, ...)
    ...
    
    # process and generate the final result
    result = process_result(subresult1, subresult2, subresult3, ...)
    # clear status

递归需要考虑的点

传参与返回值

递归调用通常携带上一层的参数到下一层，这里边要考虑是传值还是传引用，参数在下一层的操作中是否会发生变化，要操作的变量是全局变量还是参数变量，待求的数据是通过参数指针方式进行传递，还是用函数返回值。如在golang中，由于slice在append操作下会扩容，会生成新的slice，一般传递slice指针。

记忆化

重复递归可使用记忆化方式，将计算过的结果保存起来，比如可以使用map来保存中间结果。

尾递归

先理解下尾调用

尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化（称为“尾调用消除”），但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。 ——wiki

func testA(a, b int) bool {
	 c := a + b
	 return testB(c)
}

函数相互调用的过程，会在内存维护一个调用栈(call stack)，新调用的函数，会形成新的栈帧（stack frame），压入栈顶，这样每个函数都有自己的执行上下文。栈帧通常包含返回地址，参数，局部变量等信息。

尾调用优化是指由于尾调用是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只需直接用内层函数的调用记录取代外层函数的调用记录就可以了。关于尾调用优化，可以参考阮一峰老师的这篇文章。

尾调用自身就是尾递归，尾递归是一种递归的写法，可以避免不断的将函数压栈最终导致堆栈溢出。通过设置一个累加参数，并且每一次都将当前的值累加上去，然后递归调用。

尾递归在普通尾调用的基础上，多出了2个特征：

• 在尾部调用的是函数自身 （Self-called）；
• 可通过优化，使得计算仅占用常量栈空间 (Stack Space)。

尾递归的优化也要看语言的支持情况。

能否用迭代来代替递归

递归由于使用了call stack，会使用额外的内存空间，如果能用迭代来代替递归，由于节省了内存空间，效率往往也会有提升，比如在计算斐波那契数列的时候可以直接使用迭代来代替递归。

递归的应用

使用递归加上一些其他的策略往往能解决复杂的问题，比如

• 递归实现分治思想（divide and conquer）
• 深度优先搜索与剪枝
• 递归与回溯的结合

具体到一些实际案例上，可以解决

• 二叉树的遍历，反转
• N皇后问题的搜索
• 解决数独问题

Java中HashMap实现

HashMap底层使用table数组存储数据

transient Node<K,V>[] table;
int size; // 键值对个数

数组存储的内容是Node，Node表示一个键值对，还有hash字段，在比较两个节点和计算节点索引时使用hash字段，另外还有一个next指针。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

至此，可以猜出java中HashMap的解决碰撞的方法使用的是拉链法

load factor

负载因子，默认0.75，负载因子是衡量在哈希表的容量被自动增加之前，哈希表被允许装多满的一个度量

threshold = capacity * load factor

默认初始容量是16，默认负载因子是0.75，因此默认threshold是12。

threshold意味着如果当前键值对个数超过这个值，则需要调整HashMap的大小，进行resize。

箱子(bin)/桶(bucket)

其实就是对应hashmap的table数组中的一个位置。

Because TreeNodes are about twice the size of regular nodes, we. use them only when bins contain enough nodes to warrant use(see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution

这里涉及到java的一个处理，当一条链表元素的个数超过TREEIFY_THRESHOLD时，会将链表转换成红黑树。当由于remove或者resize操作导致拉出来的元素减少到UNTREEIFY_THRESHOLD，会将红黑树转换成链表。

也就是说，当bins被过度填充时，才转换成红黑树。在哈希函数设计合理下，一般不会转换成红黑树。在随机哈希码下，箱中节点的频率服从泊松分布。箱子中装8个node的概率已经很低了。

* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006

putVal

用于插入或者更新操作

核心方法就是putVal，流程如下：

• 如果table还为null，则先初始化table，默认的load factor是0.75，初始容量是16，threshold是12
• 如果通过hash，查找到指定数组的位置时，发现为null，则直接在该位置放上一个node
• 否则表示有碰撞
  • 如果在数组上找到相同hash和相同key，说明是更新已存在的key的value
  • 如果是红黑树node，则使用putTreeVal处理
  • 否则从碰撞位置开始遍历链表
    • 如果找到相同的hash和key，则是更新已存在的key的value
    • 否则在链表末端拉出一个node
• 如果插入一个node后，size大于等于threshold，则进行resize

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;	// 如果table为null，则resize，初始化table，n设置为table长度
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);	// 如果没有该节点，则new一个
        else {
          	// 有碰撞
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
								// 在数组上找到相同hash和相同key，说明是更新已存在的key的value
  	            e = p;
            else if (p instanceof TreeNode)
              	// 如果是红黑树node
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
              	// 有碰撞，从碰撞位置开始遍历链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                      	// 如果碰撞位置没有拉出节点，则延长碰撞位置的链表
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash); // 链表转换成树
                        break;
                    }
                  	// 比较链表上的节点的hask和key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;	// 下一个链表节点
                }
            }
            if (e != null) { // existing mapping for key
              	// 在数组上或某条链表上找到了相同的hash和相同的key，表明是更新指定的key对应的value
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;	// 返回旧值
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();	// 如果键值对个数超过threshold，则扩容
        afterNodeInsertion(evict);
        return null;
    }

resize

resize的流程包括

• 设置新的容量和threshold为之前的2倍
• 用之前的2倍容量新建数组
• rehash，并将就数据拷贝至新数组

触发resize：当node总数大于threshold(cap * load factor)。如果大小是固定的，并且随着越来越多的元素被添加到hashmap中，那么将会有越来越多的冲突，从而维护更长的链表，因此迭代它们的时间将不再是常数，而是可能达到O(n)。因此，为了更均匀地分布节点，当其中的节点总数超过某个阈值时，调整hashmap的容量大小。

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
          	// 新的容量扩大为原来两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // 新threshold等于旧threshold扩大两倍
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // 使用默认值初始化容量和hthreshold
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;	// 更新threshold
        @SuppressWarnings({"rawtypes","unchecked"})
        // 扩容
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
  			// rehashing
        if (oldTab != null) {
	          //	遍历旧的table
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                      	// 如果只有一个node，后面没有拉链。将node rehash到新table的指定位置
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                       // 针对树节点
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // 拉出来的链表还要保持原来的顺序
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;	// rehash到低位置
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;	// rehash到高位置
                        }
                    }
                }
            }
        }
        return newTab;
    }

getNode

用于查找操作

优先找数组，然后遍历链表查找

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // 优先检查数组上的node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;	// 找到数组上的node
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)	// 树的处理
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
	              // 遍历链表上的node
  	            do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

removeNode

用于删除操作

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                  	// 树的处理
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                  	// 待删除节点为数组上的元素
                    tab[index] = node.next;	// 将待删除节点的下一个节点(可能是null)直接放到数组指定索引上
                else
                  	// 待删除节点为链表上的元素
                    p.next = node.next; 	// 直接删除这个node
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

rehashing

Rehashing is done to distribute items across the new length hashmap, so that get and put operation time complexity remains O(1)

重哈希是重新计算已存储条目(键值对)的hashcode的过程，以便在达到threshold时将它们移动到另一个更大的hashmap(所以Java文档中说不保证映射的顺序；特别是，它不能保证node顺序会随着时间保持不变)。为了维持O(1)的查找，如果不rehashing，resize没有意义。但是hashmap为get和put操作提供的总体时间复杂度(O(1))将长期摊销rehasing过程。

简单理解

hashmap的容量就是bucket/array的元素个数，也即数组的长度。如一开始n=4，容量为16，bucket的个数为16，数组长度16，load Factor是0.75，当放到13个key-value时，超过了13 > threshold limit(16 * 0.75)，这时候hashmap就要进行扩容了，以维持get，put的性能。这时n=5，即bucket扩展到了32（即加倍），这时候需要对已经存在的节点进行重新计算哈希值（rehashing），均摊放置到这32个bucket中。

为什么哈希表的时间复杂度是O(1)?

Hashmap best and average case for Search, Insert and Delete is O(1) and worst case is O(n).

哈希表底层存储一般是数组，通过拉链法解决冲突，通过指定key去定位桶是通过hash函数来实现的，hash函数时间复杂度是O(1)的，我们可以说，在实现了良好的hash函数的前提下，桶内的项查找才会花费预期的O(1)时间。虽然会有搜索链表(或平衡树)的情况，但是从节点分布均匀，摊销的角度来说，哈希表的搜索，插入和删除平均时间复杂度是O (1)。

参考

• 尾调用优化
• Stack frame layout on x86-64
• What is Load factor and Rehashing in Hashmap?
• How time complexity of Hashmap get() and put() operation is O(1)? Is it O(1) in any condition?

[Hypon-liu]

还把源码加自己理解贴出来，厉害～

[miniKid]

学习了尾递归，通过把函数调用放在最后一句返回语句，使得外层函数不需要再保存相关信息，直接使用内层函数的变量环境。尾递归需要语言支持，也需要注意分辨尾递归的定义，只能是返回函数，不能对函数做额外的操作。

[redhare-ma]

今日最佳，很详细

[maxzxc0110]

同学总结的太好了，佩服，学习！

[rateyu]

有深度，有思考，向你学习

[0291]

good

[leecj]

niubility

[YinDongFang]

👍学习到了

[Spicycrayfish]

入选本周最佳

[MonroeHe]

太仔细了

[108851027]

赞，太棒了

[lkn12138]

厉害了

[justin-tse]

太优秀了，给出文章参考出处的习惯好好。