Java-Hashtable原理探究

发表于 2018-01-28 更新于 2018-12-17 分类于 Java

和 HashMap 一样，Hashtable 也是一个散列表，它存储的内容是键值对。

Hashtable 在 Java 中的定义为：

1
2
3

public class Hashtable<K,V>  
    extends Dictionary<K,V>  
    implements Map<K,V>, Cloneable, java.io.Serializable{}

从源码中我们可以看出：

Hashtable继承于Dictionary类 —— 任何可将键值映射到相应值的类的一种抽象父类。每个键和值都是对象。
实现了Map<K,V>, Cloneable, java.io.Serializable 接口

阅读全文 »

系统设计-缓存算法

发表于 2018-01-27 更新于 2018-12-17 分类于系统设计

在学系统设计的时候设计到了缓存过期算法。在此详细研究一下介个。

本文主要参考自详解三种缓存过期策略LFU，FIFO，LRU（附带实现代码）

缓存机制：先分配一定的缓存空间。使用数据的时候先查询缓存空间中是否有该数据的缓存。如果有的话直接拿出来。如果没有的话去其它地方查询，然后同时将查询到的结果放入缓存空间，方便下次调用。伪代码如下：

def getUser(user_id):
	user = cache.get(user_id)
    if user :
      return user
    user = database.get(user_id)
    cache.set(key, user)
    return user
  
def setUser(user):
  cache.delete(user.user_id)
  database.set(user)

缓存机制就像上面所说的那样。cache 一般是有有效期的，也就是如果缓存中这个数据过期了，那就从缓存中清理出去。而cache 的实现过程和淘汰机制不同，会导致不同的性能表现。常见的就是IFIO，LRU，LFU缓存过期策略。

FIFO(First In First Out) : 先进先出。淘汰掉很久以前进来的数据，而新数据等到之后再淘汰。也就是一个队列。
LRU (Least recently used) : 最近最少使用。淘汰最近不适用的数据
LFU (Least frequently used) : 最近使用次数最少。淘汰掉使用次数最少的页面。

阅读全文 »

系统设计-从用户系统中理解数据库与Cache

发表于 2018-01-26 更新于 2018-12-17 分类于系统设计

大纲

Memcached
用户认证 - Authentication - 保持登录状态
SQL vs NoSQL
Friendship
如何扩展？
- Sharding
- Consistent Hashing
- Replica

阅读全文 »

算法-线段树

发表于 2018-01-23 更新于 2018-12-17 分类于算法

线段树入门

本文主要参考自JustDoIT 和线段树知识点总结

线段树，类似区间树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。

线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]。线段树形如：

阅读全文 »

系统设计-设计Uber

发表于 2018-01-21 更新于 2018-12-17 分类于系统设计

大纲

RingPop
- https://github.com/uber/ringpop-node
- 一个分布式架构
- 扩展阅读 http://ubr.to/1S47b8g [Hard]
- http://bit.ly/1Yg2dnd [Hard]
TChannel https://github.com/uber/tchannel
一个高效的RPC协议 RPC: Remote Procedure Call
Google S2 https://github.com/google/s2-geometry-library-java 一个地理位置信息存储与查询的算法
Riak Dynamo DB 的开源实现

阅读全文 »

算法-位操作

发表于 2018-01-19 更新于 2018-12-17 分类于算法

Bitwise AND of Numbers Range

求m ~ n之间所有数字的与。

思路：一开始就是暴力与。但这样超时了。

参考资料[LeetCode] Bitwise AND of Numbers Range 数字范围位相与

我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110

发现了规律后，我们只要写代码找到左边公共的部分即可。

直接平移m和n，每次向右移一位，直到m和n相等，记录下所有平移的次数i，然后再把m左移i位即为最终结果，代码如下：

public int rangeBitwiseAnd(int m, int n) {
       // 统计m和n的高位相等的个数
       int counter = 0;
       while (m != n){
           m = m >> 1;
           n = n >> 1;
           ++counter;
       }
       // 将m左移counter次就是结果
       return m << counter;
   }

Single Number

给一个数组，数组中只有一个元素是单个出现的，其它都是成对出现。找到这个元素。

思路：由于x ^ 0 = x, x ^ x = 0 , 因此 x ^ x ^ y ^ z ^ z = y

public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }

Reverse Bits

将无符号整数按位反转。

public int reverseBits(int n) {
        int result = 0;
        for(int i = 0; i < 32; ++i) { // 注意：这里不可以用 n > 0的判断！因为是无符号的！
            result <<= 1;
            result += (n & 1); // n & 1 == n % 2
            n >>= 1;
        }
        return result;
    }

Number of 1 Bits

求一个无符号整数的1bit的个数

public int hammingWeight(int n) {
        int counter = 0;
        for(int i = 0; i < 32; ++i){
            counter += (n & 1);
            n >>= 1;
        }
        return counter;
    }

Maximum Product of Word Lengths

给一些str。求两个没有共有字母的word的长度乘积的最大值。

public int maxProduct(String[] words) {
    int[] bitCount = new int[words.length];
    for(int i = 0; i < words.length; ++i){
        for(char c : words[i].toCharArray()){
            bitCount[i] |= (1 << (c-'a')); // 将第c-'a'位 置为1
        }
    }
    int max = 0;
    for(int i = 0; i < words.length; ++i){
        for(int j = i + 1; j < words.length; ++j){
            if((bitCount[i] & bitCount[j]) == 0){ // 如果word[i]和word[j]的与为0，则说明没有共有的字母
                max = Math.max(words[i].length() * words[j].length(), max);
            }
        }
    }
    return max;
}

Integer Replacement

输入n,给定以下操作：

如果n是偶数，则将n替换为n/2
如果n是奇数，则将n替换为n+1或者n-1

求一个n变为1的最少操作次数

思路一，递归

private int helper(long n){
        if(n == 1) return 0;
        if(n % 2 == 0) return  1 + helper(n/2);
        else return 2 + Math.min(helper((n+1)/2), helper((n-1)/2));
    }
    public int integerReplacement(int n) {
        return helper(n);
    }

(话说这个递归改成记忆化搜索之后居然过不了)

思路二，位操作

首先，对于任意偶数，只有一个选择，即除以2，总的步数增加1。然后，对于任意奇数，无论加一或者减一，得到的必然是偶数，依然还要要除以2，步数增加2。所以归结的问题是，奇数到底是加一还是需要减一呢？

举一个简单的例子，数字5，当5+1=6时，明显不如5-1=4快，因为6除以2后又是一个奇数3，对比5-1得到的4，需要额外的两步变为4 (5->6->3->4 vs 5->4)，或者多一步数变为2 (5->6->3->2 vs 5->4->2)。其实上，数字尽可能为偶数，是最快的。

如上所述，奇数无论加减1，如果得到的数能被4整除（偶数的2倍），那么就是快的。对于任意奇数，可以写成4n+1或者4n+3的形式。适当加一或者减一，总有可能被4整除，所以实际中只要测试其中一种运算即可。这里面要考虑一个特例：3变4，因为3->2->1结束。

public int integerReplacement(int n) {
        if(n == 3) return 2;
        int total = 0;
        while (n != 1){ // n可能为负（溢出了），因此不可以用n > 1
            if(n % 2 == 0){
                n >>>= 1; // >>> 表示无符号右移
            }else if(n == 3 || (n + 1) % 4 != 0){
                --n;
            }else{
                ++n;
            }
            ++total;
        }
        return total;
    }

改进版：

public int integerReplacement(int n) {
        if(n == 3) return 2;
        int total = 0;
        while (n != 1){ // n可能为负（溢出了），因此不可以用n > 1
            if(n % 2 == 0){
                n >>>= 1; // >>> 表示无符号右移
            }else if(n == 3 || ((n + 1) & 1) == 1 || (((n + 1) >>> 1) & 1) == 1){
                // ((n + 1) & 1) == 1 表示n+1 这个数字的二进制最后一位是1，因此它一定不是4的倍数
                // (((n + 1) >> 1) & 1) == 1 表示n+1这个数字的二进制倒数第二位是1，因此它一定不是4的倍数
                --n;
            }else{
                ++n;
            }
            ++total;
        }
        return total;
    }

Hamming Distance

给两个整数，计算两个整数的二进制汉明距离

public int hammingDistance(int x, int y) {
    int bit = 1;
    int dist = 0;
    // 每次比较最低位的异或，如果异或为1，则距离+1；如果异或为0，则距离不变
    
    // 两个都不为0时
    while(x > 0 && y > 0){
        dist += ((bit & x)^(bit & y));
        x = x >> 1;
        y = y >> 1;
    }
    // 挑出一个还没为0的数字继续计算
    if(y > 0) x = y;
    while(x > 0){
        dist += (bit & x);
        x = x >> 1;
    }
    return dist;
}

另一种方式：

1
2
3

public int hammingDistance(int x, int y) {
  return Integer.bitCount(x^y);
}

系统设计-新鲜事系统

发表于 2018-01-15 更新于 2018-12-17 分类于系统设计

系统设计面试

设计某系统
- 设计微博
- 设计Facebook
- 设计滴滴、Uber
- 设计微信
- 设计点评
- 设计短网址系统 Tiny URL
- 设计NoSQL数据库
找问题
- 网站挂了怎么办
- 网站太慢怎么办
- 流量增长怎么办

阅读全文 »

Java-HashMap的原理探究

发表于 2018-01-14 更新于 2018-12-17 分类于 Java

HashMap概述

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是不保证该顺序恒久不变。

此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get和put）提供稳定的性能。

迭代colletction视图所需要的时间与HashMap实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以如果迭代性能很重要，则不能将初始容量设置得太高，或者将加载因子设置的太低。

需要注意的是，HashMap是不同步的。如果多个线程同时访问一个HashMap，若其中某个线程修改了HashMap的结构（即删除或者添加映射关系），那么必须要保持外部同步。

阅读全文 »

算法-图

发表于 2018-01-11 更新于 2018-12-17 分类于算法

大纲

Graph
- Clone Graph
- Topological Sorting 拓扑排序
搜索
- DFS
- BFS 两个场景
  - 图的遍历，Graph Traversal
  - 简单图求最短路径，Shortest Path in Simple Graph

阅读全文 »

算法-栈

发表于 2017-12-25 更新于 2018-12-17 分类于算法

大纲

线性
- 队列 - Queue
- 栈 - Stack
- 哈希 - Hash
树形
- 堆/优先队列 - Heap / Priority Queue
- Tire
- TreeMap

阅读全文 »

甲乙小朋友的房子

Java-Hashtable原理探究

系统设计-缓存算法

系统设计-从用户系统中理解数据库与Cache

算法-线段树

线段树入门

系统设计-设计Uber

算法-位操作

相关题

Bitwise AND of Numbers Range

Single Number

Reverse Bits

Number of 1 Bits

Maximum Product of Word Lengths

Integer Replacement

Hamming Distance

系统设计-新鲜事系统

Java-HashMap的原理探究

HashMap概述

算法-图

算法-栈