java中短網址服務TinyURL生成算法的示例分析

這篇文章給大家分享的是有關java中短網址服務TinyURL生成算法的示例分析的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

1、生成全局唯一的數字

這本質是一個分布式ID的問題。如果簡單處理的話可以借用redis的incr操作這樣每次取到的ID都是單調遞增且唯一的。另外一種方式是借用mysql,這里不是借用mysql的主鍵的auto_incr特性。而是每一臺應用來請求時分配一個范圍比如 s1 [100-200], s2 來請求的時候就分配 [201-301]，本質是利用樂觀鎖進行一個cas操作。

如果不想借助外部去生成ID的話，可以用UUID算法。UUID長度12個字節組成由，以下幾個部分組成。

• 4個字節表示的Unix timestamp,

• 3個字節表示的機器的ID

• 2個字節表示的進程ID

• 3個字節表示的計數器

UUID是一類算法的統稱，具體有不同的實現。優點是每臺機器可以獨立產生ID，理論上保證不會重復，所以天然是分布式的，缺點是生成的ID太長，不僅占用內存，而且索引查詢效率低。

還有一個叫Twitter Snowflake算法，本質上看起來與UUID有些類似。 

總的來說redis,mysql解決方案就比較簡單直接可以滿足大部分的場景，如果要保證高性能和高可用的話UUID和Twitter Snowflake算法就更合適，實現起來相對復雜一些。  

2、進制轉換

這個操作就相對簡單了。直接上代碼：

/**
 * 短鏈接生成
 */
public class TinyURL {
 
  public static final char[] array =
          {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
          'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', 'a', 's', 'd',
          'f', 'g', 'h', 'j', 'k', 'l', 'z', 'x', 'c', 'v', 'b', 'n', 'm',
          'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P', 'A', 'S', 'D',
          'F', 'G', 'H', 'J', 'K', 'L', 'Z', 'X', 'C', 'V', 'B', 'N', 'M'};
 
  public static Map<Character, Integer> charValueMap = new HashMap<Character, Integer>();
 
  //初始化map
  static {
    for (int i = 0; i < array.length; i++) charValueMap.put(array[i], i);
  }
 
 
  public static void main(String[] args) {
    for (int i = 0; i < 100; i++) {
      long number = Long.MAX_VALUE - i;
      String decimalStr = numberConvertToDecimal(number, 62);
      System.out.println(number + " 轉換成 " + decimalStr);
      long toNumber = decimalConvertToNumber(decimalStr, 62);
      System.out.println(decimalStr + " 轉換成 " + toNumber);
    }
  }
 
 
  /**
   * 把數字轉換成相對應的進制,目前支持(2-62)進制
   *
   * @param number
   * @param decimal
   * @return
   */
  public static String numberConvertToDecimal(long number, int decimal) {
    StringBuilder builder = new StringBuilder();
    while (number != 0) {
      builder.append(array[(int) (number - (number / decimal) * decimal)]);
      number /= decimal;
    }
    return builder.reverse().toString();
  }
 
  /**
   * 把進制字符串轉換成相應的數字
   * @param decimalStr
   * @param decimal
   * @return
   */
  public static long decimalConvertToNumber(String decimalStr, int decimal) {
    long sum = 0;
    long multiple = 1;
    char[] chars = decimalStr.toCharArray();
    for (int i = chars.length - 1; i >= 0; i--) {
      char c = chars[i];
      sum += charValueMap.get(c) * multiple;
      multiple *= decimal;
    }
    return sum;
  }
 
 
}

這里面有個小優化就是用charValueMap記錄每個字符對應的數值，這是一個用空間換時間的策略優化，把O(n)的時間降為O(1)。

另外通常我們要記錄短網址與長網址的對應的關系，相對于直接存儲短網址的而言，存儲對應的數值ID會更省空間。

感謝各位的閱讀！關于“java中短網址服務TinyURL生成算法的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！