Programmer Competency Matrix I

I 数据结构
Q1 数组和链表的差异

A1: 
1）数组在内存中是逐个存放的，也就是说倘若数组的第一个元素在地址A,则数组第二个元素就在地址A+1。

而链表则不是，链表每个节点没有相对固定的位置关系。某个节点在地址A其后的节点不一定是A+1,而在内存的其他空闲区域，呈现一种随机的状态。

2）数组一旦显式的被申明后，其大小就固定了，不能动态进行扩充。而链表则可以，可以动态生成节点并且添加到已有的链表后面。

3）链表灵活，但是空间和时间额外耗费较大；数组大小固定，元素位置固定，但是操作不灵活，且容易浪费空间，但是时间耗费较小，尤其是元素变化不大的时候效率很高。双向链表比单向的更灵活，但是空间耗费也更大

。。。。。

链表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。 
链表顾名思义，要把各个元素链接起来才算撒。   
  通常链表每一个元素都要保存一个指向下一个元素的指针（单链表）。   
  双链表的化每个元素即要保存到下一个元素的指针，还要保存一个上一个元素的指针。   
  循环链表则把最后一个元素中保存下一个元素指针指向第一个元素。   
数组是一组具有相同类型和名称的变量的集合。这些变量称为数组的元素,每个数组元素都有一个编号,
这个编号叫做下标,我们可以通过下标来区别这些元素。数组元素的个数有时也称之为数组的长度。

Q2 字典的特性

A2 
字典 ( Dictionary) 定义为“键- 值对” (Key-Value Pair) 的集合.最基本的操作包括：find( 查找 ) 、 add( 插入 ) 、 remove( 删除 ) ，分别用来从字典中检索数据、插入数据和删除数据。
系统数据字典可分为三个层次：

第一：平台层--->指系统依赖的底层平台级数据字典，如：标准字段类型；这个层次只能在开发平台阶段修改，其余不允许修改。

第二：应用层--->指系统应用逻辑涉及的数据字典，如上述的用户状态类型；这个只能在开发系统的时候修改，客户无权修改。

第三：表现层---->指最终客户自己定义的数字典，如国家分类；这个客户可随时动态添加

这个三个层次都得做控制。所以在数据字典表中得定数据字典平台标志字段，通过这个字段可控制。

当然数据字典还分生命周期，这个在上面也体现了。
生命周期又分为：开发，测试，维护。这些阶段数据字典的操作规则都不同的。
java中数据字典的应用: http://hbiao68.iteye.com/blog/1513200

Q3 简述哈希表的实现和如何处理冲突

Q4 简述优先队列及其实现

Q5 简述B树,B+树，斐波那契堆，红黑树特性和使用场景
http://www.kongch.com/2011/09/why-b-tree/
http://blog.csdn.net/v_JULY_v/article/details/6530142

总结
通过以上介绍，大致将B树，B+树，B*树总结如下：

B树：有序数组+平衡多叉树；数据存在于非叶子节点上

B+树：有序数组链表+平衡多叉树；数据只存在于叶子上。

B*树：一棵丰满的B+树。

走进搜索引擎的作者梁斌老师针对B树、B+树给出了他的意见：

“B+树还有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。

比如要查 5-10之间的，B+树一把到5这个标记，再一把到10，然后串起来就行了，B树就非常麻烦。B树的好处，就是成功查询特别有利，因为树的高度总体要比B+树矮。不成功的情况下，B树也比B+树稍稍占一点点便宜。    B树比如你的例子中查，17的话，一把就得到结果了。
有很多基于频率的搜索是选用B树，越频繁query的结点越往根上走，前提是需要对query做统计，而且要对key做一些变化。    另外B树也好B+树也好，根或者上面几层因为被反复query，所以这几块基本都在内存中，不会出现读磁盘IO，一般已启动的时候，就会主动换入内存。”


TreeMap:  http://www.ibm.com/developerworks/cn/java/j-lo-tree/
对于 TreeMap 而言，由于它底层采用一棵“红黑树”来保存集合中的 Entry，这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低：当 TreeMap 添加元素时，需要通过循环找到新增 Entry 的插入位置，因此比较耗性能；当从 TreeMap 中取出元素时，需要通过循环才能找到合适的 Entry，也比较耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于：TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态，TreeSet 中所有元素总是根据指定排序规则保持有序状态。

红黑树
红黑树是一种自平衡排序二叉树，树中每个节点的值，都大于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值，这确保红黑树运行时可以快速地在树中查找和定位的所需节点。