兴趣新闻
public class ArraySort {
@SuppressWarnings("unchecked")
public static void main(String[] args){
String[] sum ={"ac","ca","bk","w","d1"};
Arrays.sort(sum);
for(int i = 0;i<sum.length;i++){
System.out.println(sum[i]);
}
}
}
package test.map;
import java.util.Arrays;
public class ArraySort {
public static void main(String[] args){
int[] sum ={1,4,2,3,6,7,8,11,10,20};
Arrays.sort(sum);
for(int i = 0;i<sum.length;i++){
System.out.println(sum[i]);
}
}
}
昨天看到了叶漂兄的Post：《Hashtable的烦恼！》，文中提出有关Hashtable中键值对(key/value pair)排序的问题。其实所谓键值对的排序问题，实质上就是键(key)排序的问题。而一直以来，我都认为Hashtable中的键排序是随机的，因为自己有限的编程经验告诉我：键值对插入的顺序不同会影响键值对的输出顺序，实际上就是影响到键的输出顺序了。在和quitgame讨论了一番之后，我发觉问题远没有自己想象中那么简单。于是对Hashtable进行了一番看似钻牛角尖的研究，终于对Hashtable中键排序有了正确的认识。引发我去思考的C#代码可以参考叶漂的原文，以下给出的是Java的代码(公司里只有WSAD，也只能对Java代码进行分析了)：含了对自己的另一个实例的引用next，用以指向另外一个Entry。而图中标有数字的部分是一个Entry数组，数字就是这个Entry数组的index。那么往Hashtable增加键值对的时候，index会根据键的hashcode、Entry数组的长度共同决定，从而决定键值对存放在Entry数组的哪个位置。从这种意义来说，当键一定，Entry数组的长度一定的情况下，所得到的index肯定是相同的，也就是说插入顺序应该不会影响输出的顺序才对。然而，还有一个重要的因素没有考虑，就是计算index出现相同值的情况。譬如代码中 "sichuan" 和 "anhui"，所得到的index是相同的，在这个时候，Entry的链表功能就发挥作用了：put方法通过Entry的next属性获得对另外一个Entry的引用，然后将后来者放入其中。根据debug得出的结果，"sichuan", "anhui"的index同为2，"hunan"的index为6，"beijing"的index为1，在输出的时候，会以index递减的方式获得键值对。很明显，会改变的输出顺序只有"sichuan"和"anhui"了，也就是说输出只有两种可能："hunan" - "sichuan" - "anhui" - "beijing"和"hunan" - "anhui" - "sichuan" - "beijing"。以下是运行了示例代码之后，Hashtable的结果：和quitgame，给了我思考的机会，也让我感到了基础知识的匮乏，看来是要补补基础知识了。
[补充]：在Hashtable的实现代码中，有一个名为rehash的方法用于扩充Hashtable的容量。很明显，当rehash方法被调用以后，每一个键值对相应的index也会改变，也就等于将键值对重新排序了。这也是往不同容量的Hashtable放入相同的键值对会输出不同的键值对序列的原因。在Java中，触发rehash方法的条件很简单：hahtable中的键值对超过某一阀值。默认情况下，该阀值等于hashtable中Entry数组的长度×0.75
public class TestHashtable 
{
public static void main(String[] args){
Hashtable ht = new Hashtable(); ht.put("sichuan","chengdu"); //改变以下四行代码的顺序，可能会改变输出内容的顺序 ht.put("hunan","changsha"); ht.put("beijing","beijing"); ht.put("anhui","hefei"); Enumeration e = ht.keys(); while(e.hasMoreElements()) { Object key = e.nextElement(); Object value = ht.get(key); System.out.println(key + " " + value + " " + key.hashCode() + " " + value.hashCode());
} }
}
为了讲述Hashtable键排序的问题，我们先来看Hashtable的结构图：
从上面的结构图可以看出，Hashtable的实质就是一个数组＋链表。图中的Entry就是链表的实现，Entry的结构中包
以上的讨论基于Java展开的，在C#中的Hashtable实现会有所不同，但是我相信两者的设计应该是差不多的。感谢叶漂
表空间就只谈相关的数据文件
首先明确概念:表空间是ORACLE内部定义的一个概念,是为了统一ORACLE物理和逻辑
上的结构而专门建立的,从物理上来说,一个表空间是由具体的一个或多个磁盘上数
据文件构成的(至少1对1,可以1对多),从逻辑上来说一个表空间是由具体的一个或
多个用户模式下的表,索引等等里面的数据所构成的.
因此从用户的角度来看是不应该看到磁盘上物理的数据文件的,其从小到大的视角是
这样的关系:
字段值 --> 记录值 --> 表数据 --> 用户 --> 表空间 --> ORACLE
而从一个ORACLE DBA的视角来看应是这样的关系:
数据文件 --> 表空间 --> ORACLE
综合一下,也就是说在ORACLE中表不可能单独存在,一定隶属于某一个用户,而某一
用户的数据必定存在于某个表空间中.
唯一索引
组合索引
反向键索引
位图索引
a）数据文件A，格式为：关键词、IP地址、时间，记录条数为1000万左右，该文件是无序排列的。
b）数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。
要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。
请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。（至少要给出关键算法和设计思路）
2，一个简单的论坛系统，以数据库储存如下数据：
用户名，email，主页，电话，联系地址，发帖标题，发帖内容，回复标题，回复内容。
每天论坛访问量300万左右，更新帖子10万左右。
请给出数据库表结构设计，并结合范式简要说明设计思路。
tal_userInfo(userId,userName,email,homepage,telphone,addrees)
tal_article(aritcleId,title,content,mainId)
package bai;
public class Sort {
/**
* 交换数据（交换空间）
*/
public void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public int partition(int a[], int low, int high) {
int pivot, p_pos, i;
p_pos = low;
pivot = a[p_pos];
for (i = low + 1; i <= high; i++) {
if (a[i] > pivot) {
p_pos++;
swap(a, p_pos, i);
}
}
swap(a, low, p_pos);
return p_pos;
}
public void quicksort(int a[], int low, int high) {
int pivot;
if (low < high) {
pivot = partition(a, low, high);
quicksort(a, low, pivot - 1);
quicksort(a, pivot + 1, high);
}
}
public static void main(String args[]) {
int vec[] = new int[] { 37, 47, 23, -5, 19, 56 };
int temp;
//选择排序法(Selection Sort)
long begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 0; i < vec.length; i++) {
for (int j = i; j < vec.length; j++) {
if (vec[j] > vec[i]) {
temp = vec[i];
vec[i] = vec[j];
vec[j] = temp;
}
}
}
}
long end = System.currentTimeMillis();
System.out.println("选择法用时为：" + (end - begin));
//打印排序好的结果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
// 冒泡排序法(Bubble Sort)
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 0; i < vec.length; i++) {
for (int j = i; j < vec.length - 1; j++) {
if (vec[j + 1] > vec[j]) {
temp = vec[j + 1];
vec[j + 1] = vec[j];
vec[j] = temp;
}
}
}
}
end = System.currentTimeMillis();
System.out.println("冒泡法用时为：" + (end - begin));
//打印排序好的结果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
//插入排序法(Insertion Sort)
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 1; i < vec.length; i++) {
int j = i;
while (vec[j - 1] < vec[i]) {
vec[j] = vec[j - 1];
j--;
if (j <= 0) {
break;
}
}
vec[j] = vec[i];
}
}
end = System.currentTimeMillis();
System.out.println("插入法用时为：" + (end - begin));
//打印排序好的结果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
//快速排序法(Quick Sort)
Sort s = new Sort();
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
s.quicksort(vec, 0, 5);
}
end = System.currentTimeMillis();
System.out.println("快速法用时为：" + (end - begin));
//打印排序好的结果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
}
}
class AntMoves {
public static void main(String args[]) {
int length = 27;
int [] pose = {1,2,3,4,5};
System.out.println("max->"+max(pose,length));
System.out.println("max->"+min(pose,length));
}
public static int max(int pose[],int len){
int max;
int []temp = new int[pose.length];
for (int i = 0; i < pose.length; i++) {
temp[i] = len - pose[i];
}
return max(temp);
}
public static int min(int pose[],int len){
int []sum = new int[5];
for(int i= pose.length-1;i>0;i--){
if(len-pose[i]>pose[i]){
sum [i] = pose[i];
}else{
sum[i] = len - pose[i];
}
}
return max(sum);
}
public static int max(int pose[]){
int max = pose[0];
for(int i=0;i<pose.length;i++){
if(max<pose[i]){
max = pose[i];
}
}
return max;
}
/**
* 插入排序(从小到大）
*/
public static int[] sort(int pose[]){
for (int i = 1; i < pose.length; i++) {
int j = i;
while (pose[j - 1] > pose[i]) {
pose[j] = pose[j - 1];
j--;
if (j <= 0) {
break;
}
}
pose[j] = pose[i];
}
return pose;
}
}
例如，如下的数据库表是符合第一范式的：
| 字段1 | 字段2 | 字段3 | 字段4 |
而这样的数据库表是不符合第一范式的：
| 字段1 | 字段2 |
字段3
|
字段4 | |
| 字段3.1 | 字段3.2 | |||
很显然，在当前的任何关系数据库管理系统（DBMS）中，傻瓜也不可能做出不符合第一范式的数据库，因为这些DBMS不允许你把数据库表的一列再分成二列或多列。因此，你想在现有的DBMS中设计出不符合第一范式的数据库都是不可能的。
第二范式（2NF）：数据库表中不存在非关键字段对任一候选关键字段的部分函数依赖（部分函数依赖指的是存在组合关键字中的某些字段决定非关键字段的情况），也即所有非关键字段都完全依赖于任意一组候选关键字。
假定选课关系表为SelectCourse(学号, 姓名, 年龄, 课程名称, 成绩, 学分)，关键字为组合关键字(学号, 课程名称)，因为存在如下决定关系：
(学号, 课程名称) → (姓名, 年龄, 成绩, 学分)
这个数据库表不满足第二范式，因为存在如下决定关系：
(课程名称) → (学分)
(学号) → (姓名, 年龄)
即存在组合关键字中的字段决定非关键字的情况。
由于不符合2NF，这个选课关系表会存在如下问题：
(1) 数据冗余：
同一门课程由n个学生选修，"学分"就重复n-1次；同一个学生选修了m门课程，姓名和年龄就重复了m-1次。
(2) 更新异常：
若调整了某门课程的学分，数据表中所有行的"学分"值都要更新，否则会出现同一门课程学分不同的情况。
(3) 插入异常：
假设要开设一门新的课程，暂时还没有人选修。这样，由于还没有"学号"关键字，课程名称和学分也无法记录入数据库。
(4) 删除异常：
假设一批学生已经完成课程的选修，这些选修记录就应该从数据库表中删除。但是，与此同时，课程名称和学分信息也被删除了。很显然，这也会导致插入异常。
把选课关系表SelectCourse改为如下三个表：
学生：Student(学号, 姓名, 年龄)；
课程：Course(课程名称, 学分)；
选课关系：SelectCourse(学号, 课程名称, 成绩)。
这样的数据库表是符合第二范式的，消除了数据冗余、更新异常、插入异常和删除异常。
另外，所有单关键字的数据库表都符合第二范式，因为不可能存在组合关键字。
第三范式（3NF）：在第二范式的基础上，数据表中如果不存在非关键字段对任一候选关键字段的传递函数依赖则符合第三范式。所谓传递函数依赖，指的是如果存在"A → B → C"的决定关系，则C传递函数依赖于A。因此，满足第三范式的数据库表应该不存在如下依赖关系：
关键字段 → 非关键字段x → 非关键字段y
假定学生关系表为Student(学号, 姓名, 年龄, 所在学院, 学院地点, 学院电话)，关键字为单一关键字"学号"，因为存在如下决定关系：
(学号) → (姓名, 年龄, 所在学院, 学院地点, 学院电话)