需要事务吗?No,nosql+1
需要丰富的 sql query 吗?no,nosql+1
想偷懒吗?tiny url需要写的代码不复杂,nosql+1
qps高吗?2k,不高。sql+1
scalability 要求多高?存储和 qps 都不高,单机都能搞定。sql+1
- sql 需要自己写代码来 scale
- nosql,这些都帮你做了
是否需要 sequential ID?取决于你的算法
long ur 转成一个 6 位的 short url。给出一个长网址,返回一个短网址。
实现两个方法:
longToShort(url)
把一个长网址转换成一个以http://tiny.url/
开头的短网址shortToLong(url)
把一个短网址转换成一个长网址标准:
[a-zA-Z0-9]
. 比如: abcD9E
用两个哈希表:
短网址是固定的格式: “http://tiny.url/” + 6个字符, 字符可任意。
为避免重复, 我们可以按照字典序依次使用, 或者在随机生成的基础上用一个集合来记录是否使用过。
如取 long url的 MD5 的最后 6 位:
随机取一个 6 位的 shortURL,若没使用过,就绑定到改 long url。
public String long2Short(String url) {
while(true) {
String shortURL = randomShortURL();
if (!databse.filter(shortURL=shortURL).exists()) {
database.create(shortURL=shortURL, longURL=url);
return shortURL;
}
}
}
public class TinyUrl {
public TinyUrl() {
long2Short = new HashMap<String, String>();
short2Long = new HashMap<String, String>();
}
/**
* @param url a long url
* @return a short url starts with http://tiny.url/
*/
public String longToShort(String url) {
if (long2Short.containsKey(url)) {
return long2Short.get(url);
}
while (true) {
String shortURL = generateShortURL();
if (!short2Long.containsKey(shortURL)) {
short2Long.put(shortURL, url);
long2Short.put(url, shortURL);
return shortURL;
}
}
}
/**
* @param url a short url starts with http://tiny.url/
* @return a long url
*/
public String shortToLong(String url) {
if (!short2Long.containsKey(url)) {
return null;
}
return short2Long.get(url);
}
private String generateShortURL() {
String allowedChars = "0123456789" + "abcdefghijklmnopqrstuvwxyz" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
Random rand = new Random();
String shortURL = "http://tiny.url/";
for (int i = 0; i < 6; i++) {
int index = rand.nextInt(62);
shortURL += allowedChars.charAt(index);
}
return shortURL;
}
}
优点:实现简单
缺点:生成短链接的速度,随着短链接越多而越慢
关系型数据库表:只需Short key和 long url两列,并分别建立索引
也可使用 nosql,但需要建立两张表:
Base62:
6 位可表示的不同 URL:
优点:效率高
缺点:强依赖于全局的自增 id
public class TinyUrl {
public static int GLOBAL_ID = 0;
private HashMap<Integer, String> id2url = new HashMap<Integer, String>();
private HashMap<String, Integer> url2id = new HashMap<String, Integer>();
private String getShortKey(String url) {
return url.substring("http://tiny.url/".length());
}
private int toBase62(char c) {
if (c >= '0' && c <= '9') {
return c - '0';
}
if (c >= 'a' && c <= 'z') {
return c - 'a' + 10;
}
return c - 'A' + 36;
}
private int shortKeytoID(String short_key) {
int id = 0;
for (int i = 0; i < short_key.length(); ++i) {
id = id * 62 + toBase62(short_key.charAt(i));
}
return id;
}
private String idToShortKey(int id) {
String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
String short_url = "";
while (id > 0) {
short_url = chars.charAt(id % 62) + short_url;
id = id / 62;
}
while (short_url.length() < 6) {
short_url = "0" + short_url;
}
return short_url;
}
/**
* @param url a long url
* @return a short url starts with http://tiny.url/
*/
public String longToShort(String url) {
if (url2id.containsKey(url)) {
return "http://tiny.url/" + idToShortKey(url2id.get(url));
}
GLOBAL_ID++;
url2id.put(url, GLOBAL_ID);
id2url.put(GLOBAL_ID, url);
return "http://tiny.url/" + idToShortKey(GLOBAL_ID);
}
/**
* @param url a short url starts with http://tiny.url/
* @return a long url
*/
public String shortToLong(String url) {
String short_key = getShortKey(url);
int id = shortKeytoID(short_key);
return id2url.get(id);
}
}
因为要用到自增 id,所以只能用关系型 DB 表:
id主键、long url(索引)