算法 -- IT技术博客大学习 -- 共学习共进步！

HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行 map.put(String,Obect)方法时，系统将调用String的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的存储位置。

• 面试题 – 为什么我的朋友圈不见了？

有如下一个场景，某个服务需要构建一个列表数据返回给调用方（调用方通常是客户端），服务本身是一个数据聚合器，它由内部多个远程服务的数据聚合而生成。在正常情况下，需要将所有内部服务的结果全获取成功后再返回。但是在一个大系统中，多个服务中某个服务出现不稳定的概率会比较大，当出现如图远程服务3不可用的时候，有3种不同的解决思路。

• B-树

1972 年 R. Bayer 和 E. McCreight 的论文（参考资料 [1]）提出了 B- 树。B- 树是一棵平衡树，与一般的平衡二叉树（AVL，红黑树等）不同的是，B- 树的每个节点最多可以拥有 m（m>=2）个元素，（m+1）个子节点，并且所有的叶子节点位于同一层。B- 树的查找和插入的时间复杂度和二叉树一样，都是 O(logn)，但因为每个节点保存的元素比较多（一般是几十个到几百个之间），树的高度比一般的二叉树要小很多，访问硬盘次数更少，在数据不能全部加载到内存的时候比一般的二叉树效率要好。

• 为什么长尾数据的翻页技术实现复杂

在list长度较少时候，我们可以直接的使用数据库的翻页功能，如LIMIT offset, row_count，根据经验，在大部分场景下，单个业务的list数据长度99%在1000条以下，在数据规模较小时候，上面的方法非常适合。但剩下的1%的数据可能多达100万条，在数据规模较大的时候，当访问offset较大的数据，上述方法非常低效，但在实现方案的时候不能忽视这些超大数据集的问题，因此要实现一个适合各种变长list的翻页方案，考虑到数据的长尾问题，并没有简单高效的方案。这也体现了常说的80%+的时间在优化20%-的功能。

• 短网址服务的构建

短网址服务说白了就是URL映射，将较长的URL映射成短字符串。短址本质上是实现了一个映射函数 f(x)-> y 。对于每一个 y, 能够找到唯一的一个 x 使得 f(x) = y。即不能产生一短URL地址对应多个长URL。

• JSON和JSONP的区别

先前的概念中对JSON还是比较熟悉，对JSONP不是特别的清楚，整理完相关知识发现才豁然开朗。简单的说JSON是一种数据交换格式，而JSONP是一种非官方跨域数据交互协议。JSON是“暗号”，而JSONP则是接头方式。一个是描述信息的格式，一个是信息传递双方约定的方法。

• 深入剖析 redis 数据结构 redisObject

redis 是 key-value 存储系统，其中 key 类型一般为字符串，而 value 类型则为 redis 对象(redis object)。redis 对象可以绑定各种类型的数据，譬如 string、list 和 set。

• 如何使用1M的内存排序100万个8位数

今天看到这篇文章，颇为震撼，感叹算法之“神通”。借助于合适的算法可以完成看似不可能的事情。

• 如何让玩家相信游戏是公平的

去赌场参观过的同学应该都见过那种押大小的骰子游戏。庄家投掷三枚骰子，把骰盅盖住，玩家可以押大或小。开盅后，如果发现三个数字之和大于等于 11 就算大，小于等于 10 就算小。如果你猜对了，庄家就 1 赔 1 算给你筹码；否则输掉筹码。另外，还可以以不同赔率压数字，或压三个相同。为了保障庄家利益，三个相同的数字算不大不小。从概率上讲，这让长时间内庄家必胜。概率分析见这里。如果把这个游戏搬到网络上如何呢？

• 初探Thrift客户端异步模式

初步掌握了thrift异步客户端的用法，我们即可在需要的时候使用，或者优化当前的程序。由于这种提供的异步模式必须基于HTTP传输层，使用有一定的局限性。之后将会继续研究是否可以在TAsyncChannel的基础上，开发支持其他传输层的接口。

• 什么是二维码？有什么用？

二维码是用某种特定的几何图形按一定规律在平面（二维方向上）分布的黑白相间的图形记录数据符号信息的。通常分为堆叠式二维码和矩阵式二维码。二维码的原理可以简单概括为：在矩阵相应元素位置上用“点”表示二进制“1”，用“空”表示二进制“0”，“点”和“空”的排列组成代码。现在所看到的二维码绝大多数是“QR码”，QR码是“Quick Response”（快速反应）的缩写，由日本Denso-Wave公司发明。二维码的名称是相对与一维码来说的，相比“一维码（比如条形码）”存储的数据量更大；可以包含数字、字符，及中文文本等混合内容；有一定的容错性（在部分损坏以后可以正常读取）；空间利用率高等。这篇文章整理的是QR Code 相关的知识。

• 使用HBase EndPoint（coprocessor）进行计算

拿row counter这个简单例子来说，我要统计总行数，如果每个region 告诉我他又多少行，然后把结果告诉我，我再将他们的结果汇总一下，不就行了么？现在的问题是hbase没有提供这种接口，来统计每个region的行数，那是否我们可以自己来实现一个呢？没错，正如本文标题所说，我们可以自己来实现一个Endpoint，然后让hbase加载起来，然后我们远程调用即可。

• C语言结构体里的成员数组和指针

单看这文章的标题，你可能会觉得好像没什么意思。你先别下这个结论，相信这篇文章会对你理解C语言有帮助。

• 深入剖析 redis 数据结构 ziplist

在 redis 中，list 有两种存储方式：双链表(LinkedList)和压缩双链表(ziplist)。双链表即普通数据结构中遇到的，在 adlist.h 和 adlist.c 中实现。压缩双链表以连续的内存空间来表示双链表，压缩双链表节省前驱和后驱指针的空间(8B)，这在小的 list 上，压缩效率是非常明显的；压缩双链表在 ziplist.h 和 ziplist.c 中实现。

• 生成特定分布随机数的方法

生成随机数是程序设计里常见的需求。一般的编程语言都会自带一个随机数生成函数，用于生成服从均匀分布的随机数。不过有时需要生成服从其它分布的随机数，例如高斯分布或指数分布等。有些编程语言已经有比较完善的实现，例如Python的NumPy。这篇文章介绍如何通过均匀分布随机数生成函数生成符合特定概率分布的随机数，主要介绍Inverse Ttransform和Acceptance-Rejection两种基础算法以及一些相关的衍生方法。

• 在2048里能够得到的最大的数是多少？

Michael Brand 在 Using your Head is Permitted 趣题站 2014 年 4 月的谜题中提出了一个这样的问题：在最近非常流行的小游戏 2048 中，你能得到的最大的数是多少？

• 用牛顿迭代法求整数的平方根

这是一个挺常见的面试题，解法也五花八门。下面的代码用牛顿迭代法解决这个问题。因为输入和输出都是整数，所以只要前后两项相差小于1，就可以终止了。。。。

• 关于libmemcached中的crc的实现

libmemcached备受青睐，号称错误信息是很详细的，比所谓的memcache模块强多了；但是，就是因为他的名气大，还是被坑了；所谓的错误信息详细在get操作时完全不存在了，不管是连接失败还是各种超时，得到的错误信息都是NOTFOUND；于是乎，我想自己用PHP写一个memcached的client，起初，我可以之实现我需要的几个方法，鉴于memcache的协议很简单，应该是比较容易完成的。

• 如何编程实现 2 + 2 = 5？

Write a program that makes 2 + 2 = 5，看到这个题目，感觉很新颖，第一个答案就是用Java实现的。用上了Java中的整型实例池的概念。以前只看到过实例池导致两个对象的指针相同的问题，即。。。。

• 小心 int 乘法溢出!

C/C++ 语言里, 绝大部分平台上 int 类型是 32 位的, 无论你的操作系统是否是 64 位的. 而一些常用的函数, 如 malloc(), 它接受的参数是 size_t 类型。。。