`
泪雨的终结
  • 浏览: 5143 次
文章分类
社区版块
存档分类
最新评论

短网址服务两种不同算法JAVA实现

阅读更多
       短网址(Short URL) ,顾名思义就是看起来很短的网址。自从twitter推出短网址服务以后,各大互联网公司都推出了自己的短网
址服务。个人感觉短网址最大的优点就是短,字符少,便于发布、传播、复制和存储。

       通过网上的搜索,感觉流传了2种短网址算法,一种是基于MD5码的,一种是基于自增序列的。
       1、基于MD5码 : 这种算法计算的短网址长度一般是5位或者6位,计算过程中可能出现碰撞(概率很小),可表达的url数量为62
的5次方或6次方。感觉google(http://goo.gl),微博用的是类似这种的算法(猜的),可能看起来比较美观。
       2、基于自增序列 : 这种算法实现比较简单,碰撞的可能性为0,可表达的URL可达无穷大,长度从1开始。貌似百度的短网址服
务(http://dwz.cn/)是这种算法.

具体算法
1、MD5码 :假设url的长度为N
    a.计算长地址的MD5码,将32位的MD码分成4段,每段8个字符
    b.将a得到的8个字符串看成一个16进制的数,与N * 6个1表示的二进制数进行&操作
    得到一个N * 6长的二进制数
    c.将b得到的数分成N段,每段6位,然后将这N个6位数分别与61进行&操作,将得到的
    数作为INDEX去字母表取相应的字母或数字,拼接就是一个长度为N的短网址。
static final char[] DIGITS = 
{ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g',
'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };


public String shorten(String longUrl, int urlLength) {
		if (urlLength < 0 || urlLength > 6) {
			throw new IllegalArgumentException("the length of url must be between 0 and 6");
		}
		String md5Hex = DigestUtils.md5Hex(longUrl);
		// 6 digit binary can indicate 62 letter & number from 0-9a-zA-Z
		int binaryLength = urlLength * 6;
		long binaryLengthFixer = Long.valueOf(StringUtils.repeat("1", binaryLength), BINARY);
		for (int i = 0; i < 4; i++) {
			String subString = StringUtils.substring(md5Hex, i * 8, (i + 1) * 8);
			subString = Long.toBinaryString(Long.valueOf(subString, 16) & binaryLengthFixer);
			subString = StringUtils.leftPad(subString, binaryLength, "0");
			StringBuilder sbBuilder = new StringBuilder();
			for (int j = 0; j < urlLength; j++) {
				String subString2 = StringUtils.substring(subString, j * 6, (j + 1) * 6);
				int charIndex = Integer.valueOf(subString2, BINARY) & NUMBER_61;
				sbBuilder.append(DIGITS[charIndex]);
			}
			String shortUrl = sbBuilder.toString();
			if (lookupLong(shortUrl) != null) {
				continue;
			} else {
				return shortUrl;
			}
		}
		// if all 4 possibilities are already exists
		return null;
	}


2、自增序列:
   a. 或者序列的自增值,将值用62进制表示。

	private AtomicLong sequence = new AtomicLong(0);

	@Override
	protected String shorten(String longUrl) {
		long myseq = sequence.incrementAndGet();
		String shortUrl = to62RadixString(myseq);
		return shortUrl;
	}

	private String to62RadixString(long seq) {
		StringBuilder sBuilder = new StringBuilder();
		while (true) {
			int remainder = (int) (seq % 62);
			sBuilder.append(DIGITS[remainder]);
			seq = seq / 62;
			if (seq == 0) {
				break;
			}
		}
		return sBuilder.toString();
	}


       MAVEN工程中的代码用2个MAP来模拟存放长-短网址的互相映射,实际使用中可能是基于数据库表配合索引或者一些分布式KV系统来实现。
分享到:
评论

相关推荐

    几个推荐算法的java实现

    - 在Java中实现slopeone算法,需要维护用户-物品的评分矩阵,并计算每个用户对不同物品的评分差异。这个过程涉及到大量的数据处理和计算,Java的面向对象特性可以很好地支持此类任务。 2. **SVD (奇异值分解)**: ...

    进程调度的两种算法JAVA实现----FCFS(先来先服务)和SJF(最短作业优先)

    本文将详细介绍两种经典的进程调度算法:FCFS(先来先服务)和SJF(最短作业优先),并以JAVA语言实现为例进行讲解。 **一、FCFS(先来先服务)** FCFS是最简单的调度算法,它按照进程到达的先后顺序进行调度。...

    各种算法 java和c语言两种实现

    每一种算法在Java和C语言中的实现都可以帮助开发者对比两种语言在抽象、内存管理和执行效率上的差异。 对于学习者来说,比较Java和C语言的算法实现可以帮助提升编程技巧,理解不同语言的优缺点。在实际工作中,根据...

    java国密算法实现

    总的来说,Java国密算法实现涉及了椭圆曲线加密和哈希函数两大核心概念,通过合理运用这些算法,可以构建安全可靠的加密通信和数据保护系统。在具体编程时,需要对算法原理有深入理解,并熟练掌握相关库的使用,以...

    经典常用算法 Java和C语言两种实现

    本资源“经典常用算法 Java和C语言两种实现”聚焦于将这些算法用两种广泛使用的编程语言——Java和C语言进行实现,旨在帮助开发者理解和应用这些基础且重要的算法。 1. **排序算法**: - **冒泡排序**:简单的比较...

    A*算法Java/C++实现

    在这个“A*算法Java/C++实现”的项目中,我们将深入探讨A*算法的核心原理以及如何在Java和C++这两种编程语言中实现它。 A*算法的关键在于它的评估函数,该函数计算每个节点的估计成本到目标,通常表示为f(n)。f(n)...

    Java实现kNN算法

    Java实现k近邻(kNN)算法是机器学习领域中一种基础且重要的算法,主要用于分类和回归问题。kNN算法基于实例的学习,它不预先建立任何模型,而是将新数据分类或预测为与其最近的k个训练样本中最常见的类别。在这个讨论...

    用java实现HS和LCR选举算法

    本文将深入探讨这两种算法的原理,并以Java语言为例,解析其实现细节。 首先,HS算法是由James Hunt和Stanley Szymanski提出的,主要应用于分布式系统中选举一个全局唯一的领导者。HS算法基于轮询机制,每个节点在...

    遗传算法Java实现

    遗传算法是一种模拟自然选择和遗传学机制的优化方法,它在解决问题时表现出强大的全局搜索能力。在Java中实现遗传算法,通常涉及以下几个关键步骤和概念: 1. **编码**: 在遗传算法中,个体通常被编码为一串数字或...

    1204 Java 遗传算法排课java sqlserver.rar_java排课算法_排课_排课系统java_遗传算法Java

    Java遗传算法排课系统是一种利用遗传算法解决复杂优化问题的软件应用。在教育领域,排课是一个典型的组合优化问题,需要考虑多方面的约束条件,如教师时间冲突、教室容量限制、课程时间安排等。遗传算法作为一种启发...

    TFIDF算法java实现

    - 提供的jar包可能是预编译的TF-IDF算法实现,可以方便地在Java项目中直接引用,而无需关心底层的实现细节。通过添加依赖或引入类路径,可以快速在自己的程序中调用TF-IDF计算功能。 6. **TF-IDF应用** - TF-IDF...

    常见算法(C,java两种实现代码)

    "常见算法(C,java两种实现代码)"这一主题涵盖了多种在计算机科学中广泛使用的算法,并通过C和Java两种编程语言进行了实现。这两种语言各有特色,C语言以其高效和底层控制而闻名,而Java则以其跨平台能力和丰富的类库...

    遗传算法java实现

    遗传算法java实现 遗传算法是一种搜索启发式算法,它模拟自然选择和遗传过程,通过选择、交叉、变异等操作来搜索最优解。在交通路线和方式规划问题中,遗传算法可以用来解决 Vehicle Routing Problem(VRP),即...

    模糊匹配算法java实现

    Java作为一种流行的编程语言,提供了丰富的库和工具来实现各种模糊匹配算法。本篇将深入探讨如何使用Java实现模糊匹配,并介绍一些核心的概念和技术。 首先,我们要理解模糊匹配的基本原理。模糊匹配是指在两个字符...

    JAVA下两种方法实现CRC算法

    JAVA下使用两种方法(计算法、查表法)实现CRC(XMODEM)算法,以及验证代码

    DES算法java实现

    ### DES算法Java实现详解 #### 一、概述 **标题**:“DES算法java实现” **描述**:“DES算法的java实现, 密码编码学的实验二” **标签**:“DES javas” 本文章详细介绍了一种利用Java语言实现的DES(Data ...

    磁盘调度算法java实现

    本项目通过Java语言实现了几种经典的磁盘调度算法,包括FIFO(先进先出)、SSTF(最短寻道时间优先)、SCAN(扫描)以及C-SCAN(循环扫描),并提供了用户界面和结果记录功能,有助于理解这些算法的工作原理。...

    经典算法Java实现

    本资源“经典算法Java实现”为Java学习者和研究人员提供了一套完整的算法实现集合,旨在帮助他们更好地理解和运用这些算法。 一、排序算法 1. 冒泡排序:基础排序算法,通过不断交换相邻的逆序元素来逐步理顺数组...

    AHP算法java实现

    在Java实现AHP算法的过程中,我们需要关注以下几个关键步骤: 1. **问题建模**:首先,根据决策问题的特点,构建一个层次结构模型。这个模型通常包括目标层、准则层和方案层。目标层代表最终要达到的目标,准则层...

Global site tag (gtag.js) - Google Analytics