HashSet的查找算法是什么?效率如何?

散装海盗 发布于 2013/01/07 19:52
阅读 8K+
收藏 4

今天遇到一个问题和别人吵起来了。。。。。还是太轻浮

大义如下:

有一个数组(有序)int[n] a = {1,2,2,3,4,4,5....} 想在其中查找某个数是不是包含在里面。

第一种解法:二分查找

第二种解法:将其导入HashSet,然后使用contains()函数

实在不明白到底哪种更快速一些,请明白人前来解释。

ps:看了下HashSet的源代码好像是用的HashMap。。。


以下是问题补充:

@散装海盗:2楼找源代码的那个,少找了一层 static int indexFor(int h, int length) { return h & (length-1); } 所以,这个应该算是直接访问,考虑到碰撞最激烈的时候应该是o(n),否则是o(1)....我错了 (2013/01/07 21:23)
@散装海盗:原题目是这样的: 数组 int[n] a={1,2,3,3,4,3,2……}数组a中的数均为正整数,求满足a[i]+a[t]=a[x],其中i,t,x均为正数,且小于等于n,求最大a[x]. 自己写了两种方法的: https://gist.github.com/4474861 https://gist.github.com/4475142 (2013/01/07 23:19)
加载中
0
逝水fox
逝水fox

二分法是O(logN) 将数组导入hashSet本身这个循环就已经是O(N)了

但至于什么快,实际跑下自有分晓,有什么好吵的

mahone
mahone
回复 @逝水fox : 单纯从理论上来分析问题,肯定是分析时间空间复杂度。。。如果考虑太多,那就只能实际跑一下了,任何分析都没用。。。
散装海盗
散装海盗
回复 @逝水fox : 题目和代码我都发出来了,请看问题补充
逝水fox
逝水fox
回复 @mahone : 重要的不只是复杂度,还有你手上实际拿着的是什么数据结构,如文中拿着一个有序数组的前提,然后一句不考虑数据结构转换的开销,讨论hashmap查找的时候O(1)带来的高效率,我觉得就实在不实际了
mahone
mahone
一般来说是这样说 二分O(longN) hash O(1) 如果只是跑一次,其实都无所谓,跑多次的话,O(1)效率就出来了。
散装海盗
散装海盗
回复 @逝水fox : 确实是的,还是应该实际测试下的说
下一页
0
散装海盗
散装海盗

...随便就来提问了,自己终结它,刚才彻底的看了下源代码(这是个好东西)

HashSet的contain方法代码:

map = new HashMap<>(initialCapacity);

public boolean contains(Object o) {
        return map.containsKey(o);
    }
用的是HashMap的方法,源代码:
public boolean contains(Object o) {
            return containsKey(o);
        }

    public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }     final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }


行了找到最后发现,就是个遍历,时间复杂度O(n),好了,二分查找完胜。

刘文波85
刘文波85
如果hash没有冲突是不要遍历的,直接定位,速度比二分会多了;hash冲突了才需要遍历,楼主代码没看懂!
散装海盗
散装海盗
回复 @canghailan : 题目和代码我都发出来了,请看问题补充
canghailan
canghailan
回复 @散装海盗 : 你还是没说对……indexFor是确定hashCode在桶中对应的位置。实际上是冲突链都非常短,很可能大部分的冲突链的长度只有1,所以所谓的遍历就是访问第一个元素就结束了。
canghailan
canghailan
回复 @散装海盗 : 建议先了解大概HashMap工作原理(散列)再看代码,不然不好理解。
canghailan
canghailan
回复 @散装海盗 : java.util.Arrays.binarySearch
下一页
0
aiasfina
aiasfina
看了一下,遍历的应该是发生碰撞的对象的链表,一般不会是 O(n)。不过话说回来,有序列表如果不是要重排序的话,一般都用折半的吧。
WanRubin
WanRubin
可以达到O(1)。
散装海盗
散装海盗
题目和代码我都发出来了,请看问题补充
0
canghailan
canghailan
package test;

import java.util.Arrays;
import java.util.BitSet;

public class TestIntSearch {
	public static void main(String[] args) {
		int[] array = { 1, 2, 2, 3, 4, 4, 5 };
		BitSet bitSet = toBitSet(array);

		System.out.println(binarySearch(array, 2));
		System.out.println(binarySearch(array, 6));
		System.out.println(bitSetSearch(bitSet, 2));
		System.out.println(bitSetSearch(bitSet, 6));
	}

	public static BitSet toBitSet(int[] array) {
		BitSet bitSet = new BitSet();
		for (int e : array) {
			bitSet.set(e);
		}
		return bitSet;
	}

	public static boolean binarySearch(int[] array, int value) {
		return Arrays.binarySearch(array, value) >= 0;
	}

	public static boolean bitSetSearch(BitSet bitSet, int value) {
		return bitSet.get(value);
	}
}
0
canghailan
canghailan
整数查找,密集的我觉得比较适合位图也就是BitSet。稀疏的散列可能更适合,二分的性能也足够优秀。
0
ilxlf
ilxlf

这个问题这样争论意义不是特别大,应该把它放在一个实际的环境中在考虑。

如果这个数组的数据读多写少,那么放在hashset里方便以后查询,肯定是比较划算的。


0
canghailan
canghailan

没考虑复杂,但是觉得这种情况用二分完全足够:

其实还可以优化,如内循环中加入2 * at < ax直接跳出等,但是意义不大。

package test;

import java.util.Arrays;

public class FindMaxNumber {
	public static void main(String[] args) {
		int[] array = randomArray(100);

		// sort
		Arrays.sort(array);

		// find max number
		boolean found = false;
		for (int x = array.length - 1; x >= 0; --x) {
			int ax = array[x];
			
			for (int t = x - 1; t >= 0; --t) {
				int at = array[t];
				int ai = ax - at;
				if (Arrays.binarySearch(array, 0, x, ai) >= 0) {
					System.out.println("a[i]:" + ai);
					System.out.println("a[t]:" + at);
					System.out.println("a[x]:" + ax);
					found = true;
					break;
				}
			}
			
			if (found) {
				break;
			}
		}
	}

	private static int[] randomArray(int n) {
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = (int) (Math.random() * i * 100) + 1;
		}
		return array;
	}
}
0
canghailan
canghailan
其实不考虑内存消耗,最快的整数查找应该是位图。
返回顶部
顶部