ARTS 06

• Algorithm 74. 搜索二维矩阵
• Review Lambdas不是函数式编程
• Tip TCP的窗口滑动
• Share ConcurrentHashMap1.7实现

---

Algorithm 74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true

示例 2:

输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false

public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        //右上角元素开始
        int i = 0;
        int j = matrix[0].length - 1;
        
        while(i < matrix.length && j >= 0){
            if(target == matrix[i][j]){
                return true;
            }
            if(target > matrix[i][j]){
                i++;
            }else{
                j--;
            }
        }
        return false;
    }

算法思路：
二维数组是有序的，从右上角来看，向左数字递减，向下数字递增。
因此从右上角开始查找，

当要查找数字比右上角数字大时，下移；
当要查找数字比右上角数字小时，左移；
如果出了边界，则说明二维数组中不存在该整数。

---

Review Lambdas不是函数式编程

Lambda表达式是Java SE 8中包含的一个新的重要特性。它们提供了一种使用表达式表示一个方法接口的简洁方法。Lambda表达式还改进了Collection库，使其更容易迭代，过滤和提取数据Collection。此外，新的并发功能可提高多核环境的性能。

Java的土地中没有人正在进行函数式编程，这是一件好事。

Java中的Lambda表达式只是一种不那么冗长的创建（略微受限制）对象的方式，因此在没有很好地理解核心功能概念的情况下采用Lambda的最可能的结果是粗糙，扭曲，难以理解，混淆的命令式面向对象的代码与一个很简洁的语法。是的，我们可以通过创建单独的类和lambda来以更冗长的方式编写完全相同的狡猾代码。

相反，即使用Java编写实际的功能代码，我们也可以用简洁的lambdas编写带有详细的类定义和对象的相同代码。

懒惰和表现
在所有性能最佳的代码未执行代码之后，懒惰可以提高性能。

---

Tip TCP的窗口滑动

图1.jpg

• 窗口左边沿向右边沿靠近为窗口合拢。这种现象发生在数据被发送和确认时。
• 当窗口右边沿向右移动时将允许发送更多的数据，我们称之为窗口张开。这种现象发
  生在另一端的接收进程读取已经确认的数据并释放了 T C P的接收缓存时。
• 当右边沿向左移动时，我们称之为窗口收缩。 Host Requirements RFC强烈建议不要使

Share ConcurrentHashMap1.7实现

为什么要使用ConcurrentHashMap？

1. 多线程环境下，HashMap会处于不安全状态。例如put操作可能会引起程序死循环，Cpu占有率达百分百，原因是多线程会导致HashMap的Entry链表形成环形数据结构，如此一来，他的next结点将永不为空，就会产生死循环获取Entry。既然不能使用HashMap，在多线程环境下就给并发容器有了登场机会。具体请参考谈谈HashMap线程不安全的体现 .
2. Hashtable效率低下。Hashtable相信很多人都知道，相比HashMap就增加了线程安全机制，在过去Hashtable就会被使用，但由于它的实现是利用synchronized来保证线程安全的，在线程竞争激烈的情况下，效率就非常低下了。原因在于当有线程访问Hashtable的同步方法时，其他线程也来访问就会进行阻塞或者轮询状态。因此效率低下，如今开发中已经鲜有人使用Hashtable了。
3. ConcurrentHashMap采用锁分段技术可有效提高并发访问率。

参考文献：
《TCP-IP详解》
Lambdas不是函数式编程
ConcurrentHashMap1.7实现