You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemds.apache.org by ba...@apache.org on 2026/06/09 12:29:52 UTC
(systemds) branch main updated: [BWARE] Add HashMapIntToInt primitive int-to-int hash map (#2478)
This is an automated email from the ASF dual-hosted git repository.
Baunsgaard pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/systemds.git
The following commit(s) were added to refs/heads/main by this push:
new c58e5b5b49 [BWARE] Add HashMapIntToInt primitive int-to-int hash map (#2478)
c58e5b5b49 is described below
commit c58e5b5b490f90f0568acf0cdd241c5d845db419
Author: Sebastian Baunsgaard <ba...@apache.org>
AuthorDate: Tue Jun 9 14:29:47 2026 +0200
[BWARE] Add HashMapIntToInt primitive int-to-int hash map (#2478)
* Add HashMapIntToInt primitive int-to-int hash map
Introduce a specialized open-addressing map storing primitive int keys and values, avoiding boxing for integer-to-integer lookups used by compressed column-group operations.
* Add component tests for HashMapIntToInt and HashMapLongInt
Cover put/get, putIfAbsent variants, collision chains, resize,
iteration, and the primitive -1 absent-sentinel contract.
* Fix HashMapIntToInt iterator skipping buckets and add randomized tests
The entry iterator advanced bucketId twice per empty bucket (pre-increment
in the loop condition plus the post-increment step), skipping entries when
buckets were unevenly filled. Dense sequential keys masked it because the
first probe always hit a non-null bucket. Add randomized tests that
cross-check against java.util.HashMap to cover imbalanced bucket layouts,
plus a chained-collision resize test, reaching full branch coverage.
---
.../runtime/compress/utils/HashMapIntToInt.java | 380 +++++++++++++++++
.../compress/util/HashMapIntToIntTest.java | 458 +++++++++++++++++++++
.../compress/util/HashMapLongIntTest.java | 59 +++
3 files changed, 897 insertions(+)
diff --git a/src/main/java/org/apache/sysds/runtime/compress/utils/HashMapIntToInt.java b/src/main/java/org/apache/sysds/runtime/compress/utils/HashMapIntToInt.java
new file mode 100644
index 0000000000..0bf8ac8217
--- /dev/null
+++ b/src/main/java/org/apache/sysds/runtime/compress/utils/HashMapIntToInt.java
@@ -0,0 +1,380 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.utils;
+
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.BiConsumer;
+
+public class HashMapIntToInt implements Map<Integer, Integer> {
+
+ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
+ static final float DEFAULT_LOAD_FACTOR = 0.75f;
+
+ protected Node[] buckets;
+
+ protected int size;
+
+ public HashMapIntToInt(int capacity) {
+ alloc(Math.max(capacity, DEFAULT_INITIAL_CAPACITY));
+ }
+
+ protected void alloc(int size) {
+ Node[] tmp = (Node[]) new Node[size];
+ buckets = tmp;
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return size == 0;
+ }
+
+ @Override
+ public boolean containsKey(Object key) {
+ return getI((Integer) key) != -1;
+ }
+
+ @Override
+ public boolean containsValue(Object value) {
+ if(value instanceof Integer) {
+ for(Entry<Integer, Integer> v : this.entrySet()) {
+ if(v.getValue().equals(value))
+ return true;
+ }
+ }
+ return false;
+
+ }
+
+ @Override
+ public Integer get(Object key) {
+ final int i = getI((Integer) key);
+ if(i != -1)
+ return i;
+ else
+ return null;
+ }
+
+ public int getI(int key) {
+
+ final int ix = hash(key);
+ Node b = buckets[ix];
+ if(b != null) {
+ do {
+ if(key == b.key)
+ return b.value;
+ }
+ while((b = b.next) != null);
+ }
+ return -1;
+
+ }
+
+ public int hash(int key) {
+ return Math.abs(Integer.hashCode(key) % buckets.length);
+ }
+
+ @Override
+ public Integer put(Integer key, Integer value) {
+ int i = putI(key, value);
+ if(i != -1)
+ return i;
+ else
+ return null;
+ }
+
+ @Override
+ public Integer putIfAbsent(Integer key, Integer value) {
+ int i = putIfAbsentI(key, value);
+ if(i != -1)
+ return i;
+ else
+ return null;
+ }
+
+ public int putIfAbsentI(int key, int value) {
+
+ final int ix = hash(key);
+ Node b = buckets[ix];
+ if(b == null)
+ return createBucket(ix, key, value);
+ else
+ return putIfAbsentBucket(ix, key, value);
+
+ }
+
+ public int putIfAbsentReturnVal(int key, int value) {
+ final int ix = hash(key);
+ Node b = buckets[ix];
+ if(b == null)
+ return createBucketReturnVal(ix, key, value);
+ else
+ return putIfAbsentBucketReturnval(ix, key, value);
+ }
+
+ public int putIfAbsentReturnValHash(int key, int value) {
+
+ final int ix = hash(key);
+ Node b = buckets[ix];
+ if(b == null)
+ return createBucketReturnVal(ix, key, value);
+ else
+ return putIfAbsentBucketReturnval(ix, key, value);
+
+ }
+
+ private int putIfAbsentBucket(int ix, int key, int value) {
+ Node b = buckets[ix];
+ while(true) {
+ if(b.key == key)
+ return b.value;
+ if(b.next == null) {
+ b.setNext(new Node(key, value, null));
+ size++;
+ resize();
+ return -1;
+ }
+ b = b.next;
+ }
+ }
+
+ private int putIfAbsentBucketReturnval(int ix, int key, int value) {
+ Node b = buckets[ix];
+ while(true) {
+ if(b.key == key)
+ return b.value;
+ if(b.next == null) {
+ b.setNext(new Node(key, value, null));
+ size++;
+ resize();
+ return value;
+ }
+ b = b.next;
+ }
+ }
+
+ public int putI(int key, int value) {
+
+ final int ix = hash(key);
+ Node b = buckets[ix];
+ if(b == null)
+ return createBucket(ix, key, value);
+ else
+ return addToBucket(ix, key, value);
+
+ }
+
+ private int createBucket(int ix, int key, int value) {
+ buckets[ix] = new Node(key, value, null);
+ size++;
+ return -1;
+ }
+
+ private int createBucketReturnVal(int ix, int key, int value) {
+ buckets[ix] = new Node(key, value, null);
+ size++;
+ return value;
+ }
+
+ private int addToBucket(int ix, int key, int value) {
+ Node b = buckets[ix];
+ while(true) {
+ if(key == b.key) {
+ int tmp = b.getValue();
+ b.setValue(value);
+ return tmp;
+ }
+ if(b.next == null) {
+ b.setNext(new Node(key, value, null));
+ size++;
+ resize();
+ return -1;
+ }
+ b = b.next;
+ }
+ }
+
+ private void resize() {
+ if(size > buckets.length * DEFAULT_LOAD_FACTOR) {
+
+ Node[] tmp = (Node[]) new Node[buckets.length * 2];
+ Node[] oldBuckets = buckets;
+ buckets = tmp;
+ size = 0;
+ for(Node n : oldBuckets) {
+ if(n != null)
+ do {
+ put(n.key, n.value);
+ }
+ while((n = n.next) != null);
+ }
+
+ }
+ }
+
+ @Override
+ public Integer remove(Object key) {
+ throw new UnsupportedOperationException("Unimplemented method 'remove'");
+ }
+
+ @Override
+ public void putAll(Map<? extends Integer, ? extends Integer> m) {
+ throw new UnsupportedOperationException("Unimplemented method 'putAll'");
+ }
+
+ @Override
+ public void clear() {
+ throw new UnsupportedOperationException("Unimplemented method 'clear'");
+ }
+
+ @Override
+ public Set<Integer> keySet() {
+ throw new UnsupportedOperationException("Unimplemented method 'keySet'");
+ }
+
+ @Override
+ public Collection<Integer> values() {
+ throw new UnsupportedOperationException("Unimplemented method 'values'");
+ }
+
+ @Override
+ public Set<Map.Entry<Integer, Integer>> entrySet() {
+ return new EntrySet();
+ }
+
+ @Override
+ public void forEach(BiConsumer<? super Integer, ? super Integer> action) {
+
+ for(Node n : buckets) {
+ if(n != null) {
+ do {
+ action.accept(n.key, n.value);
+ }
+ while((n = n.next) != null);
+ }
+ }
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder sb = new StringBuilder(size() * 3);
+ this.forEach((k, v) -> {
+ sb.append("(" + k + "→" + v + ")");
+ });
+ return sb.toString();
+ }
+
+ private static class Node implements Entry<Integer, Integer> {
+ final int key;
+ int value;
+ Node next;
+
+ Node(int key, int value, Node next) {
+ this.key = key;
+ this.value = value;
+ this.next = next;
+ }
+
+ public final void setNext(Node n) {
+ next = n;
+ }
+
+ @Override
+ public Integer getKey() {
+ return key;
+ }
+
+ @Override
+ public Integer getValue() {
+ return value;
+ }
+
+ @Override
+ public Integer setValue(Integer value) {
+ return this.value = value;
+ }
+ }
+
+ private final class EntrySet extends AbstractSet<Map.Entry<Integer, Integer>> {
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public Iterator<Entry<Integer, Integer>> iterator() {
+ return new EntryIterator();
+ }
+
+ }
+
+ private final class EntryIterator implements Iterator<Entry<Integer, Integer>> {
+ Node next;
+ int bucketId = 0;
+
+ protected EntryIterator() {
+
+ for(; bucketId < buckets.length; bucketId++) {
+ if(buckets[bucketId] != null) {
+ next = buckets[bucketId];
+ break;
+ }
+ }
+
+ }
+
+ @Override
+ public boolean hasNext() {
+ return next != null;
+ }
+
+ @Override
+ public Entry<Integer, Integer> next() {
+
+ Node e = next;
+
+ if(e.next != null)
+ next = e.next;
+ else {
+ for(bucketId++; bucketId < buckets.length; bucketId++) {
+ if(buckets[bucketId] != null) {
+ next = buckets[bucketId];
+ break;
+ }
+ }
+ if(bucketId >= buckets.length)
+ next = null;
+ }
+
+ return e;
+ }
+
+ }
+
+}
diff --git a/src/test/java/org/apache/sysds/test/component/compress/util/HashMapIntToIntTest.java b/src/test/java/org/apache/sysds/test/component/compress/util/HashMapIntToIntTest.java
new file mode 100644
index 0000000000..15c78ddb3f
--- /dev/null
+++ b/src/test/java/org/apache/sysds/test/component/compress/util/HashMapIntToIntTest.java
@@ -0,0 +1,458 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.component.compress.util;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Random;
+import java.util.Set;
+
+import org.apache.sysds.runtime.compress.utils.HashMapIntToInt;
+import org.junit.Test;
+
+public class HashMapIntToIntTest {
+
+ @Test
+ public void basic1() {
+ basic(new HashMapIntToInt(1));
+ }
+
+ @Test
+ public void basic2() {
+ basic(new HashMapIntToInt(2));
+ }
+
+ @Test
+ public void basic16() {
+ basic(new HashMapIntToInt(16));
+ }
+
+ @Test
+ public void basic100() {
+ basic(new HashMapIntToInt(100));
+ }
+
+ private void basic(HashMapIntToInt a) {
+ assertTrue(a.isEmpty());
+ assertEquals(0, a.size());
+
+ // first insert via putIfAbsentI returns the absent sentinel -1
+ assertEquals(-1, a.putIfAbsentI(1, 10));
+ assertFalse(a.isEmpty());
+ // second insert of same key keeps the existing value and returns it
+ assertEquals(10, a.putIfAbsentI(1, 99));
+ assertEquals(1, a.size());
+
+ for(int i = 2; i < 10; i++)
+ assertEquals(-1, a.putIfAbsentI(i, i * 10));
+ assertEquals(9, a.size());
+
+ // lookups
+ assertEquals(10, a.getI(1));
+ assertEquals(90, a.getI(9));
+ assertEquals(-1, a.getI(13)); // absent
+ assertEquals(Integer.valueOf(40), a.get(4));
+ assertNull(a.get(13)); // absent via boxed accessor
+
+ // containment
+ assertTrue(a.containsKey(4));
+ assertFalse(a.containsKey(42));
+ assertTrue(a.containsValue(40));
+ assertFalse(a.containsValue(41));
+
+ // iteration covers exactly the inserted entries
+ Set<Integer> keys = new HashSet<>();
+ Set<Integer> vals = new HashSet<>();
+ for(Entry<Integer, Integer> e : a.entrySet()) {
+ keys.add(e.getKey());
+ vals.add(e.getValue());
+ }
+ assertEquals(9, keys.size());
+ for(int i = 1; i < 10; i++) {
+ assertTrue(keys.contains(i));
+ assertTrue(vals.contains(i * 10));
+ }
+ }
+
+ @Test
+ public void putReturnsPreviousValue() {
+ HashMapIntToInt a = new HashMapIntToInt(4);
+ // putI returns -1 when the key is new
+ assertEquals(-1, a.putI(5, 50));
+ // putI overwrites and returns the previous value
+ assertEquals(50, a.putI(5, 51));
+ assertEquals(51, a.getI(5));
+ assertEquals(1, a.size()); // overwrite does not grow the map
+ }
+
+ @Test
+ public void putBoxedReturnsNullThenPrevious() {
+ HashMapIntToInt a = new HashMapIntToInt(4);
+ assertNull(a.put(7, 70));
+ assertEquals(Integer.valueOf(70), a.put(7, 71));
+ assertEquals(Integer.valueOf(71), a.get(7));
+ }
+
+ @Test
+ public void putIfAbsentDoesNotOverwrite() {
+ HashMapIntToInt a = new HashMapIntToInt(4);
+ assertEquals(-1, a.putIfAbsentI(3, 30));
+ assertEquals(30, a.putIfAbsentI(3, 31)); // returns existing, keeps 30
+ assertEquals(30, a.getI(3));
+ assertNull(a.putIfAbsent(8, 80));
+ assertEquals(Integer.valueOf(80), a.putIfAbsent(8, 81));
+ assertEquals(80, a.getI(8));
+ }
+
+ @Test
+ public void putIfAbsentReturnValSemantics() {
+ HashMapIntToInt a = new HashMapIntToInt(4);
+ // when absent: inserts and returns the newly stored value
+ assertEquals(40, a.putIfAbsentReturnVal(4, 40));
+ // when present: returns the existing value, does not overwrite
+ assertEquals(40, a.putIfAbsentReturnVal(4, 99));
+ assertEquals(40, a.getI(4));
+
+ // the *Hash variant has identical semantics
+ assertEquals(50, a.putIfAbsentReturnValHash(5, 50));
+ assertEquals(50, a.putIfAbsentReturnValHash(5, 99));
+ assertEquals(50, a.getI(5));
+ }
+
+ @Test
+ public void absentSignaledByMinusOneSentinel() {
+ // Design contract: the primitive int accessors (getI / putI / putIfAbsentI)
+ // signal "absent" or "no previous value" with the sentinel -1 instead of a
+ // nullable Integer. This is a deliberate performance choice to avoid boxing
+ // and null handling on the hot path, so the tests pin the -1 behavior down.
+ HashMapIntToInt a = new HashMapIntToInt(16);
+
+ // lookup of an absent key returns the sentinel (not null, no exception)
+ assertEquals(-1, a.getI(1));
+ assertEquals(-1, a.getI(Integer.MAX_VALUE));
+
+ // inserting a previously-absent key returns the sentinel (no prior value)
+ assertEquals(-1, a.putI(1, 100));
+ assertEquals(-1, a.putIfAbsentI(2, 200));
+
+ // a populated map still returns the sentinel for any missing key
+ assertEquals(-1, a.getI(3));
+
+ // Consequence of the sentinel: -1 is reserved and must not be stored as a
+ // value. A stored -1 is indistinguishable from "absent" through both the
+ // primitive and the boxed accessors, which callers are required to respect.
+ HashMapIntToInt b = new HashMapIntToInt(16);
+ b.putI(7, -1);
+ assertEquals(1, b.size()); // the entry really is stored
+ assertEquals(-1, b.getI(7)); // ...but reads back as the absent sentinel
+ assertNull(b.get(7)); // and the boxed accessor reports null as well
+ }
+
+ @Test
+ public void resizeRetainsAllEntries() {
+ // start small to force several resizes (load factor 0.75)
+ HashMapIntToInt a = new HashMapIntToInt(1);
+ final int n = 1000;
+ for(int i = 0; i < n; i++)
+ assertEquals(-1, a.putI(i, i * 2));
+ assertEquals(n, a.size());
+ for(int i = 0; i < n; i++)
+ assertEquals(i * 2, a.getI(i));
+ assertEquals(-1, a.getI(n)); // still absent after resizing
+
+ // iteration still sees every entry after resizing
+ Set<Integer> keys = new HashSet<>();
+ for(Entry<Integer, Integer> e : a.entrySet())
+ keys.add(e.getKey());
+ assertEquals(n, keys.size());
+ }
+
+ @Test
+ public void negativeAndBoundaryKeys() {
+ HashMapIntToInt a = new HashMapIntToInt(8);
+ int[] keys = {-1000, -1, 0, 1, Integer.MIN_VALUE, Integer.MAX_VALUE};
+ for(int i = 0; i < keys.length; i++)
+ a.putI(keys[i], i + 100);
+ assertEquals(keys.length, a.size());
+ for(int i = 0; i < keys.length; i++) {
+ assertEquals(i + 100, a.getI(keys[i]));
+ assertTrue(a.containsKey(keys[i]));
+ }
+ }
+
+ @Test
+ public void forEachVisitsAllEntries() {
+ HashMapIntToInt a = new HashMapIntToInt(4);
+ for(int i = 0; i < 50; i++)
+ a.putI(i, i + 1);
+ int[] count = new int[] {0};
+ long[] sum = new long[] {0};
+ a.forEach((k, v) -> {
+ count[0]++;
+ sum[0] += (v - k); // each entry contributes exactly 1
+ });
+ assertEquals(50, count[0]);
+ assertEquals(50, sum[0]);
+ }
+
+ @Test
+ public void collisionChainsPutAndGet() {
+ // capacity 16 -> 16 buckets; staying <= 12 entries avoids a resize, so
+ // keys that are congruent mod 16 deterministically share one bucket.
+ HashMapIntToInt a = new HashMapIntToInt(16);
+ assertEquals(-1, a.putI(1, 100));
+ assertEquals(-1, a.putI(17, 200)); // appended as 2nd node in the chain
+ assertEquals(-1, a.putI(33, 300)); // traverses node1 -> node2, then appends
+ assertEquals(3, a.size());
+
+ // overwrite a node deep in the chain returns the previous value
+ assertEquals(300, a.putI(33, 333));
+ assertEquals(333, a.getI(33)); // getI walks the chain to the last node
+ // a miss whose key maps to a populated bucket walks the chain, then -1
+ assertEquals(-1, a.getI(49));
+
+ // iterating a multi-node bucket exercises the iterator chain advance
+ int cnt = 0;
+ int sum = 0;
+ for(Entry<Integer, Integer> e : a.entrySet()) {
+ cnt++;
+ sum += e.getValue();
+ }
+ assertEquals(3, cnt);
+ assertEquals(100 + 200 + 333, sum);
+ }
+
+ @Test
+ public void collisionChainsPutIfAbsent() {
+ HashMapIntToInt a = new HashMapIntToInt(16);
+ // putIfAbsentI into a shared bucket: create, then append into the chain
+ assertEquals(-1, a.putIfAbsentI(1, 10));
+ assertEquals(-1, a.putIfAbsentI(17, 20));
+ assertEquals(10, a.putIfAbsentI(1, 99)); // match first node, keep 10
+ assertEquals(20, a.putIfAbsentI(17, 99)); // match deeper node, keep 20
+
+ // the *ReturnVal variants append into the same non-empty bucket
+ assertEquals(30, a.putIfAbsentReturnVal(33, 30)); // appended -> new value
+ assertEquals(30, a.putIfAbsentReturnVal(33, 99)); // present -> existing
+ assertEquals(40, a.putIfAbsentReturnValHash(49, 40)); // appended -> new value
+ assertEquals(40, a.putIfAbsentReturnValHash(49, 99)); // present -> existing
+ assertEquals(4, a.size());
+ }
+
+ @Test
+ public void toStringContainsEntries() {
+ HashMapIntToInt a = new HashMapIntToInt(16);
+ a.putI(2, 20);
+ a.putI(3, 30);
+ String s = a.toString();
+ assertTrue(s.contains("(2\u219220)")); // (2->20)
+ assertTrue(s.contains("(3\u219230)")); // (3->30)
+ }
+
+ @Test
+ public void entrySetSize() {
+ HashMapIntToInt a = new HashMapIntToInt(16);
+ for(int i = 0; i < 5; i++)
+ a.putI(i, i);
+ assertEquals(5, a.entrySet().size());
+ }
+
+ @Test
+ public void resizeWithEmptyAndChainedBuckets() {
+ // 16 buckets, load factor 0.75 -> a resize fires once size exceeds 12.
+ // Pre-seed a colliding chain in bucket 1 (keys congruent mod 16), then add
+ // distinct keys so that at resize time oldBuckets holds both a multi-node
+ // chain (if(n != null) true + chain re-put) and empty buckets (false side).
+ HashMapIntToInt a = new HashMapIntToInt(16);
+ a.putI(1, 1);
+ a.putI(17, 17); // chain node in bucket 1
+ for(int i = 2; i <= 12; i++) // distinct buckets, drives size past 12
+ a.putI(i, i);
+ assertEquals(13, a.size()); // triggers exactly one resize
+
+ assertEquals(1, a.getI(1));
+ assertEquals(17, a.getI(17));
+ for(int i = 2; i <= 12; i++)
+ assertEquals(i, a.getI(i));
+ }
+
+ @Test
+ public void resizeWithEmptyBucketsInOldTable() {
+ // A resize only fires from the collision-append path, so dense sequential
+ // keys fill every bucket before the load factor is exceeded and the old
+ // table is always full at rehash time. Here we instead pile keys that are
+ // all congruent mod 16 into a single chain: the load factor (0.75) is
+ // crossed while 15 of the 16 buckets stay empty, exercising the
+ // n == null (skip empty bucket) branch of resize()'s rehash loop.
+ HashMapIntToInt a = new HashMapIntToInt(16);
+ final int n = 13; // 13 > 16 * 0.75 triggers exactly one resize
+ for(int i = 0; i < n; i++)
+ assertEquals(-1, a.putI(i * 16, i)); // every key maps to bucket 0 at capacity 16
+ assertEquals(n, a.size());
+
+ // every entry survived the rehash over a table that contained empty buckets
+ for(int i = 0; i < n; i++)
+ assertEquals(i, a.getI(i * 16));
+ }
+
+ @Test
+ public void emptyEntrySetIteration() {
+ HashMapIntToInt a = new HashMapIntToInt(16);
+ int cnt = 0;
+ for(Entry<Integer, Integer> e : a.entrySet())
+ cnt += e.getValue();
+ assertEquals(0, cnt);
+ assertFalse(a.entrySet().iterator().hasNext());
+ assertEquals(0, a.entrySet().size());
+ }
+
+ @Test
+ public void forEachOverChain() {
+ // colliding keys (congruent mod 16) build a multi-node bucket so forEach
+ // walks the linked list within a bucket
+ HashMapIntToInt a = new HashMapIntToInt(16);
+ a.putI(1, 1);
+ a.putI(17, 1);
+ a.putI(33, 1);
+ int[] count = new int[] {0};
+ a.forEach((k, v) -> count[0]++);
+ assertEquals(3, count[0]);
+ }
+
+ @Test
+ public void containsValueNonInteger() {
+ HashMapIntToInt a = new HashMapIntToInt(4);
+ a.putI(1, 1);
+ assertFalse(a.containsValue("not-an-integer"));
+ assertFalse(a.containsValue(null));
+ }
+
+ @Test(expected = UnsupportedOperationException.class)
+ public void putAllUnsupported() {
+ new HashMapIntToInt(4).putAll(new java.util.HashMap<Integer, Integer>());
+ }
+
+ @Test(expected = UnsupportedOperationException.class)
+ public void removeUnsupported() {
+ new HashMapIntToInt(4).remove(1);
+ }
+
+ @Test(expected = UnsupportedOperationException.class)
+ public void clearUnsupported() {
+ new HashMapIntToInt(4).clear();
+ }
+
+ @Test(expected = UnsupportedOperationException.class)
+ public void keySetUnsupported() {
+ new HashMapIntToInt(4).keySet();
+ }
+
+ @Test(expected = UnsupportedOperationException.class)
+ public void valuesUnsupported() {
+ new HashMapIntToInt(4).values();
+ }
+
+ @Test
+ public void randomKeysMatchReference1() {
+ randomKeysMatchReference(1, 1, 2000);
+ }
+
+ @Test
+ public void randomKeysMatchReference16() {
+ randomKeysMatchReference(2, 16, 2000);
+ }
+
+ @Test
+ public void randomKeysMatchReferenceSmallDomain() {
+ // a small key domain relative to the entry count forces many overwrites
+ // and unevenly loaded buckets rather than a clean one-key-per-bucket layout
+ randomKeysMatchReference(3, 4, 3000);
+ }
+
+ private void randomKeysMatchReference(long seed, int capacity, int inserts) {
+ // Cross-check against java.util.HashMap under randomized, value-shifted keys
+ // so bucket load is genuinely uneven (collisions, chains, and empty buckets
+ // coexist) instead of the perfectly balanced layout that dense keys produce.
+ // Values are kept >= 0 because the primitive accessors reserve -1 as the
+ // "absent" sentinel.
+ Random r = new Random(seed);
+ HashMapIntToInt a = new HashMapIntToInt(capacity);
+ Map<Integer, Integer> ref = new HashMap<>();
+
+ for(int i = 0; i < inserts; i++) {
+ int key = r.nextInt(inserts); // domain may be smaller than #inserts -> overwrites
+ int value = r.nextInt(Integer.MAX_VALUE); // never -1
+ Integer prev = ref.put(key, value);
+ int prevI = a.putI(key, value);
+ if(prev == null)
+ assertEquals(-1, prevI); // first time we see the key
+ else
+ assertEquals(prev.intValue(), prevI); // overwrite returns previous value
+ }
+
+ assertEquals(ref.size(), a.size());
+ for(Entry<Integer, Integer> e : ref.entrySet()) {
+ assertEquals(e.getValue().intValue(), a.getI(e.getKey()));
+ assertTrue(a.containsKey(e.getKey()));
+ }
+
+ // iteration visits exactly the reference entries, nothing more or less
+ Map<Integer, Integer> seen = new HashMap<>();
+ for(Entry<Integer, Integer> e : a.entrySet())
+ assertNull("duplicate key from iterator: " + e.getKey(), seen.put(e.getKey(), e.getValue()));
+ assertEquals(ref, seen);
+
+ // a few keys outside the inserted domain must report absent
+ for(int i = 0; i < 50; i++)
+ assertEquals(-1, a.getI(inserts + r.nextInt(inserts) + 1));
+ }
+
+ @Test
+ public void randomPutIfAbsentKeepsFirstValue() {
+ // putIfAbsentI must preserve the first value stored for a key even under
+ // randomized, colliding inserts; mirror that contract with a reference map.
+ Random r = new Random(7);
+ HashMapIntToInt a = new HashMapIntToInt(2);
+ Map<Integer, Integer> ref = new HashMap<>();
+ final int inserts = 2000;
+
+ for(int i = 0; i < inserts; i++) {
+ int key = r.nextInt(inserts / 4); // small domain -> frequent collisions
+ int value = r.nextInt(Integer.MAX_VALUE); // never -1
+ if(ref.containsKey(key))
+ assertEquals(ref.get(key).intValue(), a.putIfAbsentI(key, value)); // keep first
+ else {
+ assertEquals(-1, a.putIfAbsentI(key, value));
+ ref.put(key, value);
+ }
+ }
+
+ assertEquals(ref.size(), a.size());
+ for(Entry<Integer, Integer> e : ref.entrySet())
+ assertEquals(e.getValue().intValue(), a.getI(e.getKey()));
+ }
+}
diff --git a/src/test/java/org/apache/sysds/test/component/compress/util/HashMapLongIntTest.java b/src/test/java/org/apache/sysds/test/component/compress/util/HashMapLongIntTest.java
index 404380816a..d7d314ce0e 100644
--- a/src/test/java/org/apache/sysds/test/component/compress/util/HashMapLongIntTest.java
+++ b/src/test/java/org/apache/sysds/test/component/compress/util/HashMapLongIntTest.java
@@ -20,6 +20,7 @@
package org.apache.sysds.test.component.compress.util;
import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import java.util.HashSet;
@@ -81,4 +82,62 @@ public class HashMapLongIntTest {
assertEquals(4, a.get(4));
assertEquals(-1, a.get(13));
}
+
+ @Test
+ public void absentSignaledByMinusOneSentinel() {
+ // Design contract: get / putIfAbsent signal "absent" or "no previous value"
+ // with the primitive sentinel -1 rather than a nullable Integer. This is a
+ // deliberate performance choice to avoid boxing on the hot path, so the
+ // tests pin the -1 behavior down.
+ HashMapLongInt a = new HashMapLongInt(16);
+
+ // lookup of an absent key returns the sentinel
+ assertEquals(-1, a.get(1));
+ assertEquals(-1, a.get(Long.MAX_VALUE));
+
+ // inserting a previously-absent key returns the sentinel (no prior value)
+ assertEquals(-1, a.putIfAbsent(1, 100));
+
+ // a populated map still returns the sentinel for any missing key
+ assertEquals(-1, a.get(2));
+
+ // Consequence of the sentinel: -1 is reserved and must not be stored as a
+ // value, since a stored -1 reads back as the absent sentinel.
+ HashMapLongInt b = new HashMapLongInt(16);
+ b.putIfAbsent(7, -1);
+ assertEquals(1, b.size()); // the entry really is stored
+ assertEquals(-1, b.get(7)); // ...but reads back as the absent sentinel
+ }
+
+ @Test
+ public void emptyIterator() {
+ HashMapLongInt a = new HashMapLongInt(4);
+ assertFalse(a.iterator().hasNext());
+ }
+
+ @Test
+ public void reallocateBucket() {
+ // capacity 1 forces every key into a single bucket, growing it past the
+ // initial 4 cells and exercising reallocateBucket.
+ HashMapLongInt a = new HashMapLongInt(1);
+ for(int i = 1; i <= 10; i++)
+ assertEquals(-1, a.putIfAbsent(i, i * 2));
+ assertEquals(10, a.size());
+ for(int i = 1; i <= 10; i++)
+ assertEquals(i * 2, a.get(i));
+ // re-insert an existing key returns its stored value without growing
+ assertEquals(20, a.putIfAbsent(10, 999));
+ assertEquals(10, a.size());
+ }
+
+ @Test
+ public void toStringContainsEntries() {
+ HashMapLongInt a = new HashMapLongInt(16);
+ a.putIfAbsent(2, 20);
+ a.putIfAbsent(3, 30);
+ String s = a.toString();
+ assertTrue(s.contains("HashMapLongInt"));
+ assertTrue(s.contains("2->20"));
+ assertTrue(s.contains("3->30"));
+ }
}