问题描述:
一本词典,包含了可用的全部单词,共计70000余个。要求,按规定完成编码—>译码,编码规则如下:
e jnq rwx dsy ft am civ bku lop ghz
0 111 222 333 44 55 666 777 888 999
程序的任务是:给出一串数字,从词典中找出所有的单词,如果找不到,则用原数字。
要求:
a)采用两种数据结构(hash表、其他自选),用来存放包含70000余单词的字典;
b)完成编、解码工作,对比分析数据结构对字典访问效率、算法的影响。
思路:
-
采用两种数据结构(hash表、其他自选),用来存放包含70000余单词的字典;
1) 创建一个文件用来保存下需要单词,如words.txt文件中保存了近百余个单词。
2)通过字符流读取文件,然后将单词缓存到两种数据结构哈希表和数组创建的对象中,以供后续编码和解码使用
/**
* 通过读取文件 获取字典并存储到哈希表
* @param filePath
* @return
* @throws IOException
*/
public static HashMap<Long,String> readFile2HashMap(String filePath) throws IOException {
FileReader fileReader = new FileReader(filePath);
BufferedReader bufferedReader = new BufferedReader(fileReader);
String content = null;
HashMap<Long,String> map = new HashMap<>();
while((content = bufferedReader.readLine())!=null){
map.put(CommonUtils.WordEncod(content),content);
}
bufferedReader.close();
fileReader.close();
return map;
}
/**
* 通过读取文件 获取字典并存储到数组
* @param filePath
* @return
* @throws IOException
*/
public static ArrayList<MapStruct> readFile2Arrays(String filePath) throws IOException {
FileReader fileReader = new FileReader(filePath);
BufferedReader bufferedReader = new BufferedReader(fileReader);
String content = null;
ArrayList arrayList = new ArrayList();
while((content = bufferedReader.readLine())!=null){
MapStruct mapStruct = new MapStruct();
mapStruct.code = CommonUtils.WordEncod(content);
mapStruct.content = content;
arrayList.add(mapStruct);
}
bufferedReader.close();
fileReader.close();
return arrayList;
}
- 完成编、解码工作,对比分析数据结构对字典访问效率、算法的影响。
1)哈希表解码:由于只进行单线程操作,因此选用hashMap作为哈希表数据缓存的载体。 然后通过hashMap.get()方法获取编码数字所对应的单词并记录下时间。
/**
* 哈希表查询
*
* @param number
* @param hashMap
* @param repeatTime 重复查询次数 因数据量小无法比较出来哈希表与其他数据结构的区别
*/
public static void startHashMapSerch(long number, HashMap<Long, String> hashMap,int repeatTime) {
System.out.println("开始哈希表查询!");
long startTime = System.currentTimeMillis();
String hashMapResult = "";
for (int i = 0; i < repeatTime; i++) {
hashMapResult = hashMap.get(number);
}
if (hashMapResult == null) {
System.out.println("未查询到数字" + hashMapResult + " 对应的单词");
} else {
System.out.println("查询到数字" + number + " 对应的单词为" + hashMapResult);
}
long endTime = System.currentTimeMillis();
long usedTime = (endTime - startTime);
System.out.println("结束哈希表查询!用时" + usedTime + "ms");
}
2)数组解码:选用ArrayList作为数组数据缓存的载体,通过对ArrayList遍历获取获取编码数字所对应的单词并记录下时间。
/**
* 数组查询
*
* @param number
* @param arrayList
* @param repeatTime 重复查询次数 因数据量小无法比较出来哈希表与其他数据结构的区别
*/
public static void startArrayListSerch(long number, ArrayList<MapStruct> arrayList,int repeatTime) {
System.out.println("开始数组查询!");
long startTime = System.currentTimeMillis();
String arrayListResult = null;
for (int i = 0; i < repeatTime; i++) {
for (MapStruct mapStruct : arrayList) {
if (mapStruct.code == number) {
arrayListResult = mapStruct.content;
break;
}
}
}
if (arrayListResult == null) {
System.out.println("未查询到数字" + arrayListResult + " 对应的单词");
} else {
System.out.println("查询到数字" + number + " 对应的单词为" + arrayListResult);
}
long endTime = System.currentTimeMillis();
long usedTime = (endTime - startTime);
System.out.println("结束数组查询!用时" + usedTime + "ms");
}
网友评论