lighthashmap.java

java 文件下载器。可自定义

			key = NULLKEY;
		return data[nonModifyingFindIndex(key) + 1];
	}

	private Object add(Object key, Object value, boolean bulkAdd)
	{
		if (key == null)
			key = NULLKEY;
		int idx = bulkAdd ? nonModifyingFindIndex(key) : findIndex(key);
		Object oldValue = data[idx + 1];
		if (data[idx] == null || data[idx] == THOMBSTONE)
		{
			data[idx] = key;
			size++;
		}
		data[idx + 1] = value;
		return oldValue;
	}

	public Object remove(Object key)
	{
		if (size == 0)
			return null;
		if (key == null)
			key = NULLKEY;
		int idx = findIndex(key);
		if (keysEqual(data[idx], key))
			return removeForIndex(idx);
		else
			return null;
	}

	private Object removeForIndex(int idx)
	{
		Object oldValue = data[idx + 1];
		data[idx] = THOMBSTONE;
		data[idx + 1] = null;
		size--;
		return oldValue;
	}

	public void clear()
	{
		size = 0;
		int capacity;
		for (capacity = 1; capacity < 8; capacity <<= 1);
		data = new Object[capacity * 2];
	}

	public boolean containsKey(Object key)
	{
		if (size == 0)
			return false;
		if (key == null)
			key = NULLKEY;
		return keysEqual(key, data[nonModifyingFindIndex(key)]);
	}

	public boolean containsValue(Object value)
	{
		if (value != null)
		{
			for (int i = 0; i < data.length; i += 2)
				if (value.equals(data[i + 1]))
					return true;

		} else
		{
			for (int i = 0; i < data.length; i += 2)
				if (data[i + 1] == null && data[i] != null && data[i] != THOMBSTONE)
					return true;

		}
		return false;
	}

	private final boolean keysEqual(Object o1, Object o2)
	{
		return o1 == o2 || o1 != null && o2 != null && o1.hashCode() == o2.hashCode() && o1.equals(o2);
	}

	private int findIndex(Object keyToFind)
	{
		int hash = keyToFind.hashCode() << 1;
		int probe = 1;
		int newIndex = hash & data.length - 1;
		int thombStoneIndex = -1;
		int thombStoneCount = 0;
		int thombStoneThreshold = Math.min((data.length >> 1) - size, 100);
		while (data[newIndex] != null && !keysEqual(data[newIndex], keyToFind)) 
		{
			if (data[newIndex] == THOMBSTONE)
			{
				if (thombStoneIndex == -1)
					thombStoneIndex = newIndex;
				if (++thombStoneCount * 2 > thombStoneThreshold)
				{
					compactify(0.0F);
					thombStoneIndex = -1;
					probe = 0;
					thombStoneCount = 0;
				}
			}
			newIndex = hash + probe + probe * probe & data.length - 1;
			probe++;
		}
		if (thombStoneIndex != -1 && !keysEqual(data[newIndex], keyToFind))
			return thombStoneIndex;
		else
			return newIndex;
	}

	private int nonModifyingFindIndex(Object keyToFind)
	{
		int hash = keyToFind.hashCode() << 1;
		int probe = 1;
		int newIndex = hash & data.length - 1;
		int thombStoneIndex = -1;
		for (; data[newIndex] != null && !keysEqual(data[newIndex], keyToFind) && probe < data.length >> 1; probe++)
		{
			if (data[newIndex] == THOMBSTONE && thombStoneIndex == -1)
				thombStoneIndex = newIndex;
			newIndex = hash + probe + probe * probe & data.length - 1;
		}

		if (thombStoneIndex != -1 && !keysEqual(data[newIndex], keyToFind))
			return thombStoneIndex;
		else
			return newIndex;
	}

	private void checkCapacity(int n)
	{
		int currentCapacity = data.length >> 1;
		if ((float)(size + n) < (float)currentCapacity * loadFactor)
			return;
		int newCapacity = currentCapacity;
		do
			newCapacity <<= 1;
		while ((float)newCapacity * loadFactor < (float)(size + n));
		adjustCapacity(newCapacity);
	}

	public void compactify(float compactingLoadFactor)
	{
		int newCapacity = 1;
		float adjustedLoadFactor = Math.abs(compactingLoadFactor);
		if (adjustedLoadFactor <= 0.0F || adjustedLoadFactor >= 1.0F)
			adjustedLoadFactor = loadFactor;
		for (; (float)newCapacity * adjustedLoadFactor < (float)(size + 1); newCapacity <<= 1);
		if (newCapacity < data.length / 2 || compactingLoadFactor >= 0.0F)
			adjustCapacity(newCapacity);
	}

	private void adjustCapacity(int newSize)
	{
		Object oldData[] = data;
		data = new Object[newSize * 2];
		size = 0;
		for (int i = 0; i < oldData.length; i += 2)
			if (oldData[i] != null && oldData[i] != THOMBSTONE)
				add(oldData[i], oldData[i + 1], true);

	}

	static void test()
	{
		Random rnd = new Random();
		byte buffer[] = new byte[5];
		String fillData[] = new String[0x1dc28f];
		for (int i = 0; i < fillData.length; i++)
		{
			rnd.nextBytes(buffer);
			fillData[i] = new String(buffer);
			fillData[i].hashCode();
		}

		Map m1 = new HashMap();
		Map m2 = new LightHashMap();
		System.out.println("fill:");
		long time = System.currentTimeMillis();
		for (int i = 0; i < fillData.length; i++)
			m1.put(fillData[i], buffer);

		System.out.println(System.currentTimeMillis() - time);
		time = System.currentTimeMillis();
		for (int i = 0; i < fillData.length; i++)
			m2.put(fillData[i], buffer);

		System.out.println(System.currentTimeMillis() - time);
		System.out.println("replace-fill:");
		time = System.currentTimeMillis();
		for (int i = 0; i < fillData.length; i++)
			m1.put(fillData[i], buffer);

		System.out.println(System.currentTimeMillis() - time);
		time = System.currentTimeMillis();
		for (int i = 0; i < fillData.length; i++)
			m2.put(fillData[i], buffer);

		System.out.println(System.currentTimeMillis() - time);
		System.out.println("get:");
		time = System.currentTimeMillis();
		for (int i = 0; i < fillData.length; i++)
			m1.get(fillData[i]);

		System.out.println(System.currentTimeMillis() - time);
		time = System.currentTimeMillis();
		for (int i = 0; i < fillData.length; i++)
			m2.get(fillData[i]);

		System.out.println(System.currentTimeMillis() - time);
		System.out.println("compactify light map");
		time = System.currentTimeMillis();
		((LightHashMap)m2).compactify(0.9F);
		System.out.println(System.currentTimeMillis() - time);
		System.out.println("transfer to hashmap");
		time = System.currentTimeMillis();
		new HashMap(m1);
		System.out.println(System.currentTimeMillis() - time);
		time = System.currentTimeMillis();
		new HashMap(m2);
		System.out.println(System.currentTimeMillis() - time);
		System.out.println("transfer to lighthashmap");
		time = System.currentTimeMillis();
		new LightHashMap(m1);
		System.out.println(System.currentTimeMillis() - time);
		time = System.currentTimeMillis();
		new LightHashMap(m2);
		System.out.println(System.currentTimeMillis() - time);
		System.out.println("remove entry by entry");
		time = System.currentTimeMillis();
		for (int i = 0; i < fillData.length; i++)
			m1.remove(fillData[i]);

		System.out.println(System.currentTimeMillis() - time);
		time = System.currentTimeMillis();
		for (int i = 0; i < fillData.length; i++)
			m2.remove(fillData[i]);

		System.out.println(System.currentTimeMillis() - time);
	}

	public static void main(String args[])
	{
		System.out.println("Call with -Xmx300m -Xcomp -server");
		try
		{
			Thread.sleep(5000L);
		}
		catch (InterruptedException e)
		{
			e.printStackTrace();
		}
		test();
		System.out.println("-------------------------------------");
		System.gc();
		try
		{
			Thread.sleep(300L);
		}
		catch (InterruptedException e)
		{
			e.printStackTrace();
		}
		test();
		System.out.println("\n\nPerforming sanity tests");
		Random rnd = new Random();
		byte buffer[] = new byte[25];
		String fillData[] = new String[1048];
		for (int i = 0; i < fillData.length; i++)
		{
			rnd.nextBytes(buffer);
			fillData[i] = new String(buffer);
			fillData[i].hashCode();
		}

		Map m1 = new HashMap();
		Map m2 = new LightHashMap();
		for (int i = 0; i < fillData.length * 10; i++)
		{
			int random = rnd.nextInt(fillData.length);
			m1.put(null, fillData[i % fillData.length]);
			m2.put(null, fillData[i % fillData.length]);
			if (!m1.equals(m2))
				System.out.println("Error 0");
			m1.put(fillData[random], fillData[i % fillData.length]);
			m2.put(fillData[random], fillData[i % fillData.length]);
			if (!m1.equals(m2))
				System.out.println("Error 1");
		}

		for (int i = 0; i < fillData.length / 2; i++)
		{
			int random = rnd.nextInt(fillData.length);
			m1.remove(fillData[random]);
			m2.remove(fillData[random]);
			if (!m1.equals(m2))
				System.out.println("Error 2");
		}

		for (int i = 0; i < fillData.length * 10; i++)
		{
			int random = rnd.nextInt(fillData.length);
			m1.put(fillData[random], fillData[i % fillData.length]);
			m1.put(null, fillData[i % fillData.length]);
			m2.put(fillData[random], fillData[i % fillData.length]);
			m2.put(null, fillData[i % fillData.length]);
			if (!m1.equals(m2))
				System.out.println("Error 3");
		}

		Iterator i1 = m1.entrySet().iterator();
		Iterator i2 = m2.entrySet().iterator();
		for (; i1.hasNext(); i2.remove())
		{
			i1.next();
			i1.remove();
			i2.next();
		}

		if (!m1.equals(m2))
			System.out.println("Error 4");
		m2.clear();
		for (int i = 0; i < 0x186a0; i++)
		{
			rnd.nextBytes(buffer);
			String s = new String(buffer);
			m2.put(s, buffer);
			m2.containsKey(s);
			m2.remove(s);
		}

		System.out.println("checks done");
	}




}