一种微缩因特网址的算法

一种微缩网址的算法

twitter等微博客的发展带动了一批short url应用的发展，目前网上也有好几种缩短url算法。

?

下面写的是我实际使用中的一种算法。

属于递增方式，例如

我使用的域名为abc.com

那么我存储的短网址会有

http://abc.com/aaaa

http://abc.com/aaab

http://abc.com/aaac

http://abc.com/aaad

........................

aaaa,aaab,aaac,aaad,是根据一定的规律递增短网址关键字，关键字的取值是从一个已经定义好的数组中获取。有个变量专门用来存储最后一次使用的下标，例如data="1,2,4,1"，这表明上次使用的下标，当要获取新的短网址关键字的时候，从数据库或者其他存储方式中取出data的值，然后把data的值转换为数字，并进行+1操作，来获得新的可用下标，并且把新的data值保存，以便下次使用.

代码已经提供了下载，欢迎大家提意见，本人很少写blog，语言表达能力有限，有看不明白的地方，可以提出来

?

文章为原创，若转载请注明出处

?

代码

package com.hk.bean;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;/** * 由于我使用的是a-z0-9共36个字符，所以basemap中会存储36个不同字符数组<br/> * 也就是说,微缩后的地址最多有36位 例如最长的url为<br/> * http://xxx.com/abddeeddrree09869830484aaaaaderrteae<br/> * 但是这么长的url就失去了微缩的意义，基本用到10位还是比较合理的 使用方式请看main方法 *  * @author akwei */public class ShortUrlData {/** * 预先定义要使用的字符数组，所有位置的字符都使用这里的 */private static char[] base = new char[] { 'k', '3', 'h', 'c', '0', 'p','q', '6', '1', 'v', 'i', '5', 'a', 'u', 't', 'j', '4', 's', 'z','d', 'o', 'w', '7', 'r', '2', 'l', 'g', 'b', 'm', 'f', 'y', '9','n', '8', 'x', 'e' };/** * 存储每个字符位置所使用的字符数组(由于每个位置的字符数组都会不同，所以通过map单独存储)<br/> */private static final Map<Integer, char[]> basemap = new HashMap<Integer, char[]>();/** * 此代码块的功能就是当class加载的时候，初始化basemap */static {List<String> list = new ArrayList<String>();// 把预先定义的字符放入一个集合当中for (int i = 0; i < base.length; i++) {list.add(String.valueOf(base[i]));}// 这个for循环的作用是为了生成不同的字符数组所用// 实现效果例如:// 第一个数组为 abcdefg// 那么第二个数字就是bcdefga// 第三个就是cdefgab// 第四个就是defgabc// 第五个就是efgabcd// ......// 依次循环for (int i = 0; i < base.length; i++) {// 获取基础字符集合的前i个值，组成一个新的集合endlistList<String> endlist = new ArrayList<String>(list.subList(0, i));// 获取基础字符集合的从i到结尾的所有字符集合，组成一个新的集合reslistList<String> reslist = new ArrayList<String>(list.subList(i, list.size()));// 然后把endlist放入添加到reslist的末尾// reslist就是我们需要的其中一个字符集合reslist.addAll(endlist);// 通过StringBuffer把字符集合中的字符组成一个字符串，然后生一个一个字符数组StringBuffer sb = new StringBuffer();for (String s : reslist) {sb.append(s);}char[] base_i = sb.toString().toCharArray();// 生成的字符数组存入basemap中// basemap中的key-value例如// key:0 value:[a,b,c,d,e,f,g]// key:1 value:[b,c,d,e,f,g,a]// key:2 value:[c,d,e,f,g,a,b]// key:3 value:[d,e,f,g,a,b,c]// key:4 value:[e,f,g,a,b,c,d]basemap.put(i, base_i);}}/** * 保存到数据库中的id */private int oid;/** * 保存到数据库中的下标字符串例如 data=" 1,4,5,6" */private String data;public int getOid() {return oid;}public void setOid(int oid) {this.oid = oid;}public String getData() {return data;}public void setData(String data) {this.data = data;}/** * 把data的值转化为一个int[],此int[]中存储的就是每个字符最后使用过的字符数组的下标<br/> * 例如:<br/> * data=1,2,4,2<br/> * basemap中的key-value <br/> * key:0 value:[a,b,c,d,e,f,g]<br/> * key:1 value:[b,c,d,e,f,g,a]<br/> * key:2 value:[c,d,e,f,g,a,b]<br/> * key:3 value:[d,e,f,g,a,b,c]<br/> * 那么最后一次使用的短网址关键字就是bdgf，每个字符都是与basemap中相应位置的数组对应的 *  * @return 把data的值转化为一个int[] */private int[] getDataList() {String[] s = this.data.split(",");int[] arr = new int[s.length];int i = 0;for (String ss : s) {arr[i++] = Integer.parseInt(ss);}return arr;}/** * 根据最后一次的下标数组int[]，计算获得一个可以使用的int[]<br/> * 例如<br/> * data=1,2,4,2<br/> * basemap中的key-value <br/> * key:0 value:[a,b,c,d,e,f,g]<br/> * key:1 value:[b,c,d,e,f,g,a]<br/> * key:2 value:[c,d,e,f,g,a,b]<br/> * key:3 value:[d,e,f,g,a,b,c]<br/> * key:4 value:[e,f,g,a,b,c,d]<br/> * 通过此方法，返回 一个数字数组[1,2,4,3]<br/> * 如果data=1,2,4,6<br/> * 通过此方法，返回 一个数字数组[1,2,5,0]<br/> * 如果data=6,6,6,6<br/> * 由于4位的字符已经用完，需要升级位数到5为，返回 一个数字数组[0,0,0,0,0]<br/> * 运行此方法，data的值会相应的变化 *  * @return 返回一个可以使用的int[]下标数组 */private int[] getNextDataList() {// 获得最后使用的下标数组int[] arr = this.getDataList();// 此参数的意义是是否数组长度发生了变化boolean is_arr_length_changed = false;// 此循环的目的就是把获得的下标数组中从最后一位开始+1，用来获得一个可用下标数组// 例如 basemap中存储为// key:0 value:[a,b,c,d,e,f,g]<br/>// key:1 value:[b,c,d,e,f,g,a]<br/>// key:2 value:[c,d,e,f,g,a,b]<br/>// key:3 value:[d,e,f,g,a,b,c]<br/>// key:4 value:[e,f,g,a,b,c,d]<br/>// int[]=[1,2,4,6]// 经过循环后获得的就是 int[]=[1,2,5,0]// 例如 int[]=[1,2,3,0]// 经过循环后获得的就是 int[]=[1,2,3,1]// 例如 int[]=[6,6,6,6]// 经过循环后获得的就是 int[]=[0,0,0,0,0]for (int i = arr.length - 1; i >= 0; i--) {int res = this.add(i, arr[i]);arr[i] = res;if (res == 0) {// 如果==0，说明下标已经到了最后一位,+1后会返回0，(类似于1+9=10,结果变为2位数，需要进位)is_arr_length_changed = true;// 变为0后，前一位下标肯定要进行变化，所以继续循环，把前一位下标也+1continue;}// 如果>0，说明不需要进位if (res > 0) {is_arr_length_changed = false;break;}}StringBuilder sb = new StringBuilder();// 如果int[]数组长度没有变化，则直接给data赋值if (!is_arr_length_changed) {for (int i = 0; i < arr.length; i++) {sb.append(arr[i]).append(",");}sb.deleteCharAt(sb.length() - 1);this.data = sb.toString();return arr;}// 如果int[]数组长度改变了,那么就用一个新的数组，新数组的值为arr中的值，最后一位值为0int[] arr2 = new int[arr.length + 1];for (int i = 0; i < arr2.length; i++) {arr2[i] = 0;sb.append(arr2[i]).append(",");}sb.deleteCharAt(sb.length() - 1);this.data = sb.toString();return arr2;}/** * 获得一个可以用的缩短后的url关键字<br/> * 例如<br/> * data=1,2,4,2<br/> * basemap中的key-value <br/> * key:0 value:[a,b,c,d,e,f,g]<br/> * key:1 value:[b,c,d,e,f,g,a]<br/> * key:2 value:[c,d,e,f,g,a,b]<br/> * key:3 value:[d,e,f,g,a,b,c]<br/> * key:4 value:[e,f,g,a,b,c,d]<br/> * 通过此方法，返回 一个数字数组[1,2,4,3]，通过这个数组到basemap中获得相应位置的字符，返回值为对应[1,2,4,3]的 bdgg<br/> * 如果data=1,2,4,6<br/> * 通过此方法，返回 一个数字数组[1,2,5,0]，返回值为对应[1,2,5,0]的 bdae<br/> * 如果data=6,6,6,6<br/> * 由于4位的字符已经用完，需要升级位数到5为，返回 一个数字数组[0,0,0,0,0]，返回值为对应[0,0,0,0,0]的 abcde<br/> *  * @return 返回的字符串就是我们需要的缩短url后的关键字 */public String getNextShortKey() {int[] arr = this.getNextDataList();StringBuilder sb = new StringBuilder();for (int i = 0; i < arr.length; i++) {// sb.append(base[arr[i]]);char[] ch = basemap.get(i);sb.append(ch[arr[i]]);}return sb.toString();}/** * 字符数组下标+1，如果到尾部，则归0 <br/> * 例如<br/> * basemap中的key-value <br/> * key:0 value:[a,b,c,d,e,f,g]<br/> * key:1 value:[b,c,d,e,f,g,a]<br/> * key:2 value:[c,d,e,f,g,a,b]<br/> * key:3 value:[d,e,f,g,a,b,c]<br/> * key:4 value:[e,f,g,a,b,c,d]<br/> * data=1,2,4,6<br/> * 1对应basemap中key=0时的数组中字符b<br/> * 2对应basemap中key=1时的数组中字符c<br/> * 4对应basemap中key=2时的数组中字符g<br/> * 6对应basemap中key=3时的数组中字符c<br/> * add(0,1)=2<br/> * 参数0代表1,2,4,6中的下标0<br/> * 参数1代表1,2,4,6中的下标0的值1，也就是key=0时的数组[a,b,c,d,e,f,g]的下标1<br/> * 返回值2代表1下标后移一位后的结果,也就是key=0时的数组[a,b,c,d,e,f,g]的下标2<br/> * add(3,6)=0<br/> * 返回值0代表下标已经在最后一位了，如果再次后移，就要让下标移到开始位置，也就是key:4 value:[e,f,g,a,b,c,d]中<br/> * 下标6代表数组中最后一位，不能再次后移，只能回到0的位置，(简单的说就是1+9=10，个位肯定是0，需要进位) *  * @param digits 字符所在位数 例如 abcd c所在第2位 * @param i 字符数组下标 * @return */private int add(int digits, int i) {char[] ch = basemap.get(digits);int res = (i + 1) % ch.length;return res;}public static void main(String[] args) {ShortUrlData o = getShortUrlDataFromDB();System.out.println(o.getNextShortKey());System.out.println(o.getData());// 例如从数据库取出}/** * 假设是从数据库中取出 *  * @return */private static ShortUrlData getShortUrlDataFromDB() {ShortUrlData o = new ShortUrlData();o.setOid(1);o.setData("5,2,1,35");// o.setData("35,35,35");return o;}}

?