Java: Implement map using array as storage

In this post, I am going to implement ArrayMap, which use array as internal data structure. Since most of the operations have O(n) time complexity, it can be used only for the map with small number of elements (e.g less than 100).

 

Find the below working application.

 

ArrayMap.java

package com.sample.app.algos;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class ArrayMap<K, V> implements Map<K, V> {

	/**
	 * Both <key, value> pairs stored in data array like {key1, value1, key2,
	 * value2....}
	 */
	private Object[] data;

	public ArrayMap() {
	}

	public ArrayMap(Map<? extends K, ? extends V> map) {
		putAll(map);
	}

	private int getKeyIndex(Object key) {
		if (key == null) {
			return -1;
		}

		if (isEmpty()) {
			return -1;
		}

		for (int keyIndex = 0; keyIndex < data.length; keyIndex += 2) {
			if (key.equals(data[keyIndex])) {
				return keyIndex;
			}
		}

		return -1;
	}

	@Override
	public int size() {
		return data == null ? 0 : data.length >> 1;
	}

	@Override
	public boolean isEmpty() {
		return (data == null) || (data.length == 0);
	}

	@Override
	public boolean containsKey(Object key) {
		return getKeyIndex(key) >= 0;
	}

	@Override
	public boolean containsValue(Object value) {
		if (value == null) {
			return false;
		}

		if (isEmpty()) {
			return false;
		}

		for (int valueIndex = 1; valueIndex < data.length; valueIndex += 2) {
			if (value.equals(data[valueIndex])) {
				return true;
			}
		}

		return false;
	}

	@Override
	public V get(Object key) {
		int keyIndex = getKeyIndex(key);

		return keyIndex < 0 ? null : (V) data[keyIndex + 1];
	}

	@Override
	public V put(K key, V value) {
		if ((key == null) || (value == null)) {
			throw new NullPointerException("Key or value must not be null.");
		}

		if (data == null) {
			data = new Object[] { key, value };
			return null;
		}
		int keyIndex = getKeyIndex(key);

		if (keyIndex > 0) {
			V oldValue = (V) data[keyIndex + 1];
			data[keyIndex + 1] = value;
			return oldValue;
		}

		int currentDataLength = data.length;
		Object[] newMapArr = new Object[currentDataLength + 2];

		System.arraycopy(data, 0, newMapArr, 0, currentDataLength);

		newMapArr[currentDataLength] = key;
		newMapArr[currentDataLength + 1] = value;

		data = newMapArr;

		return null;

	}

	@Override
	public V remove(Object key) {
		int keyIndex = getKeyIndex(key);

		if (keyIndex < 0) {
			return null;
		}

		V oldValue = (V) data[keyIndex + 1];
		int oldLen = data.length;

		if (oldLen == 2) {
			data = null;
			return oldValue;
		}

		Object[] newMapArr = new Object[oldLen - 2];
		System.arraycopy(data, 0, newMapArr, 0, keyIndex);
		System.arraycopy(data, keyIndex + 2, newMapArr, keyIndex, oldLen - keyIndex - 2);
		data = newMapArr;

		return oldValue;
	}

	@Override
	public final void putAll(Map<? extends K, ? extends V> otherMap) {
		if (isEmpty()) {
			data = new Object[2 * otherMap.size()];

			int index = 0;
			for (Entry<? extends K, ? extends V> entry : otherMap.entrySet()) {
				if ((entry.getKey() == null) || (entry.getValue() == null)) {
					throw new NullPointerException("Key or value must not be null.");
				}

				data[index++] = entry.getKey();
				data[index++] = entry.getValue();
			}
			return;
		}

		// Copy current key, value pairs to newDataArray
		int oldLen = data.length;
		Object[] newDataArray = new Object[oldLen + (2 * otherMap.size())];
		System.arraycopy(data, 0, newDataArray, 0, oldLen);

		int newIndex = oldLen;
		for (Entry<? extends K, ? extends V> entry : otherMap.entrySet()) {
			if ((entry.getKey() == null) || (entry.getValue() == null)) {
				throw new NullPointerException("Key or value must not be null.");
			}

			int existKeyIdx = getKeyIndex(entry.getKey());

			if (existKeyIdx >= 0) {
				newDataArray[existKeyIdx + 1] = entry.getValue();
				continue;
			}
			newDataArray[newIndex++] = entry.getKey();
			newDataArray[newIndex++] = entry.getValue();

		}

		if (newIndex < newDataArray.length) {
			Object[] adjustedArrayBySize = new Object[newIndex];
			System.arraycopy(newDataArray, 0, adjustedArrayBySize, 0, newIndex);
			newDataArray = adjustedArrayBySize;
		}

		data = newDataArray;

	}

	@Override
	public void clear() {
		data = null;
	}

	@Override
	public Set<K> keySet() {
		if (isEmpty()) {
			return Collections.emptySet();
		}

		Set<K> keys = new LinkedHashSet<K>();
		for (int keyIndex = 0; keyIndex < data.length; keyIndex += 2) {
			keys.add((K) data[keyIndex]);
		}
		return Collections.unmodifiableSet(keys);
	}

	@Override
	public Collection<V> values() {
		if (isEmpty()) {
			return Collections.emptySet();
		}

		List<V> values = new ArrayList<V>(data.length >> 1);
		for (int valueIndex = 1; valueIndex < data.length; valueIndex += 2) {
			values.add((V) data[valueIndex]);
		}
		return Collections.unmodifiableList(values);
	}

	private class ArrayMapEntry implements Entry<K, V> {
		private final int keyIndex;

		ArrayMapEntry(int keyIndexInArray) {
			keyIndex = keyIndexInArray;
		}

		@Override
		public K getKey() {
			return (K) data[keyIndex];
		}

		@Override
		public V getValue() {
			return (V) data[keyIndex + 1];
		}

		@Override
		public V setValue(V value) {
			if (value == null) {
				throw new NullPointerException("Key or value must not be null.");
			}

			V oldValue = getValue();
			data[keyIndex + 1] = value;
			return oldValue;
		}

		@Override
		public int hashCode() {
			return getKey().hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof ArrayMap.ArrayMapEntry)) {
				return false;
			}

			ArrayMapEntry other = (ArrayMapEntry) obj;

			return getKey().equals(other.getKey()) && getValue().equals(other.getValue());
		}
	}

	@Override
	public Set<java.util.Map.Entry<K, V>> entrySet() {
		if (isEmpty()) {
			return Collections.emptySet();
		}

		Set<java.util.Map.Entry<K, V>> entries = new LinkedHashSet<Entry<K, V>>();

		for (int kIdx = 0; kIdx < data.length; kIdx += 2) {
			entries.add(new ArrayMapEntry(kIdx));
		}
		return Collections.unmodifiableSet(entries);
	}

	public String toString() {
		if (isEmpty()) {
			return "";
		}

		StringBuilder builder = new StringBuilder();
		builder.append("{\n");

		for (int keyIndex = 0; keyIndex < data.length; keyIndex += 2) {
			builder.append("\t<").append(data[keyIndex]).append(",").append(data[keyIndex + 1]).append(">").append("\n");
		}

		builder.append("}");
		return builder.toString();
	}

}

ArrayMapDemo.java

package com.sample.app.algos;

import java.util.Map;

public class ArrayMapDemo {

	public static void main(String[] args) {
		Map<Integer, Integer> map = new ArrayMap<>();

		map.put(1, 2);
		map.put(2, 3);
		map.put(3, 5);
		map.put(4, 7);

		System.out.println(map);
	}

}

Output

{
	<1,2>
	<2,3>
	<3,5>
	<4,7>
}

 

 

You may like

Interview Questions

Can an interface extend multiple interfaces in Java?

instanceof operator behavior with interface and class

Call the main method of one class from other class using reflection

Java: Check whether a class exists in the classpath or not

How to get the name of calling class that invoke given method?