Puzzle about the iterative sequence

danielchang-Z commented

2018-09-30 03:21:26 +00:00

(Migrated from github.com)

A pleasure that LinkedHashMap has been added.

While I have a different point about the iterative sequence. The sequence should order by the key last time put in instead of the first time put in.

This situation is caused by the func named LinkedHashMap.Put:

// Put inserts key-value pair into the map.
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (m *Map) Put(key interface{}, value interface{}) {
	if _, contains := m.table[key]; !contains {
		m.ordering.Append(key)
	}
	m.table[key] = value
}

Test case as follows:

func main() {
	lhm := linkedhashmap.New()
	lhm.Put("a", 1)
	lhm.Put("b", 2)
	lhm.Put("c", 3)
	lhm.Put("a", 4)
	lhm.Each(func(k, v interface{}) { fmt.Println(k, v) })
}

I except the output like

b 2
c 3
a 4

, but the result is

a 4
b 2
c 3

.

A pleasure that LinkedHashMap has been added. While I have a different point about the iterative sequence. The sequence should order by the key last time put in instead of the first time put in. This situation is caused by the func named LinkedHashMap.Put: ``` // Put inserts key-value pair into the map. // Key should adhere to the comparator's type assertion, otherwise method panics. func (m *Map) Put(key interface{}, value interface{}) { if _, contains := m.table[key]; !contains { m.ordering.Append(key) } m.table[key] = value } ``` Test case as follows: ``` func main() { lhm := linkedhashmap.New() lhm.Put("a", 1) lhm.Put("b", 2) lhm.Put("c", 3) lhm.Put("a", 4) lhm.Each(func(k, v interface{}) { fmt.Println(k, v) }) } ``` I except the output like ``` b 2 c 3 a 4 ``` , but the result is ``` a 4 b 2 c 3 ``` .

emirpasic commented

2018-10-02 08:00:27 +00:00

(Migrated from github.com)

@danielzhangy that behaviour is by design, I just have to write that in the documentation.

Not sure why java does it this way, but I used their ideology: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html

... . Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.). ...

I followed their documentation as not to be "smart" about it, but it can be implemented either way.

@danielzhangy that behaviour is by design, I just have to write that in the documentation. Not sure why java does it this way, but I used their ideology: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html > ... . Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.). ... I followed their documentation as not to be "smart" about it, but it can be implemented either way.

danielchang-Z commented

2018-10-04 12:03:29 +00:00

(Migrated from github.com)

@emirpasic I think the reason that java does it this way is that java wants the iterative sequence of LinkedHashMap to be close to the k-v entry input order, it is more ergonomic.

emirpasic commented

2018-10-04 12:12:48 +00:00

(Migrated from github.com)

@danielzhangy yes, I suppose it all depends at how we define "insertion".

Does placing the same element into set or map constitute insertion? According to Java, they don't treat it as a new insertion. I am really not sure about this one, might get philosophical :D

I will leave this question open in case somebody else has an opinion on this, for now I leave it with the Java's idea of what "insertion" really means.

@danielzhangy yes, I suppose it all depends at how we define "insertion". Does placing the same element into set or map constitute insertion? According to Java, they don't treat it as a new insertion. I am really not sure about this one, might get philosophical :D I will leave this question open in case somebody else has an opinion on this, for now I leave it with the Java's idea of what "insertion" really means.

danielchang-Z commented

2018-10-05 07:06:31 +00:00

(Migrated from github.com)

@emirpasic yes, it depends on the definition of "insertion".

Thanks to your reminder, I read the source code of Java 11. Java treats the same element placing in two different ways, it depends on the initial condition named accessOrder. If accessOrder is false, Java treats the same element placing as updating, otherwise, Java treats it as a special new insertion(updating the value of mapping key and moving the element to the tail of order list).

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }


void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

@emirpasic yes, it depends on the definition of "insertion". Thanks to your reminder, I read the source code of Java 11. Java treats the same element placing in two different ways, it depends on the initial condition named accessOrder. If accessOrder is false, Java treats the same element placing as updating, otherwise, Java treats it as a special new insertion(updating the value of mapping key and moving the element to the tail of order list). ``` final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } } ```

emirpasic commented

2018-10-05 11:08:41 +00:00

(Migrated from github.com)

@danielzhangy thanks for the research, it gave me an idea that it's best to have both. I think I'll add that option also to the LinkedHashSet and LinkedHashMap to configure this behavior or specialized functions that behave in one or the other way. Hwever, oI am still not sure what the default behavior should be, should the same element be evicted upon reinsertion and added to the end or should the default behavior follow Java's default behavior, i.e. no change in insertion order.

danielchang-Z commented

2018-10-07 06:43:36 +00:00

(Migrated from github.com)

@emirpasic I prefer to choose current implementation as default behavior, and make another way as optional, by considering the performance of operation. So what do you think?

emirpasic commented

2018-10-11 13:12:24 +00:00

(Migrated from github.com)

@danielzhangy i agree with you and i'll leave the current implementation as default, but will provide a way to modify this behavior.

mort666 closed this issue

2026-09-07 17:04:12 +00:00

Rows
Columns

Puzzle about the iterative sequence #93