TL;DR

オブジェクト: 保証されることもあるが、混乱を招くので保証されないものとして扱うべきである。
Map: 挿入順。

ちなみに、この記事ではわざわざ触れないが、Set、WeakMap、WeakSetも挿入順で列挙される。

仕様のレベルで保証されているかを議論しているのであって、ある特定の実装では順番が保証されていることもある。

`Map`のキーの列挙順は保証される

まずは素直な方から行く。

const map = new Map();
map.set("a", 1);
map.set("b", 2);
map.set("c", 3);
map.set("b", 4);
console.log([...map.entries()]); // => [["a", 1], ["b", 4], ["c", 3]]

キーの順番は挿入順になることが保証されている。
同一のキーで上書いた場合、キーの順番に関しては変化せず、値だけが書き換わる挙動になる。
この挙動は仕様で保証されている。

さらにもう一つ補足しておくと、コンストラクタからキーと値を一気に流し込んだ場合も、setを順番通りに複数回呼んだときと同じ挙動になる。
この挙動は仕様で保証されている。

const map = new Map([["a", 1], ["b", 2], ["c", 3], ["b", 4]]);
console.log([...map.entries()]); // => [["a", 1], ["b", 4], ["c", 3]]

オブジェクトのプロパティの列挙順は保証されることもある

正確に言うと、保証されるメソッドとされないメソッドがある。
保証される場合も、直感的とは言い難い順番で列挙される。
したがって、オブジェクトのプロパティの列挙順に依存するコードを書くべきではない。

列挙順が保証されるメソッド

Object.assign
Object.defineProperties
Object.getOwnPropertyNames
Object.getOwnPropertySymbols
Reflect.ownKeys

列挙順が保証されないメソッド

Object.keys
for-in（正確にはメソッドではないが）
JSON.parse
JSON.stringify

列挙順が保証される場合の列挙順

次の順に列挙する。

$0$〜$2^{32}-2$¹の整数として解釈可能な文字列であるプロパティを、整数として解釈した場合の昇順で列挙する
$0$〜$2^{32}-2$の整数として解釈できない文字列であるプロパティを、挿入順に列挙する
シンボルであるプロパティを、挿入順に列挙する

なぜこんなことになっているのか

ECMAScript 5以前は、オブジェクトのプロパティの列挙順は（少なくとも仕様レベルでは）全く保証されていなかった。
ここに動きが出たのがECMAScript 2015である。
ECMAScript 2015では、オブジェクトのプロパティについても列挙順を保証しようということになった。

しかし、ある特定の列挙順を仕様で決めてしまうと、互換性が崩れかねない問題がある。
たとえば、実装依存のある特定の列挙順を前提としているコードが壊れてしまわないだろうか？
ECMAScript、ひいてはWebの技術は、仕様の明快さよりも今あるものが動くことを大事にする哲学を持つ。
そういうことで、ECMAScript 5以前からあるメソッドは、あえて列挙順を保証しないままとすることになった。

まとめ

オブジェクトのプロパティの列挙順に依存するコードを書くべきではない。
この目的ではMapを使うべきである。
Mapのキーは挿入順で列挙される。

参考リンク

Does JavaScript Guarantee Object Property Order?

$2^{32}-2$は配列のインデックスとして解釈可能な最大値。配列の要素数の最大値が$2^{32}-1$であるためこうなる。 ↩

[JavaScript] オブジェクト/Mapのキーの列挙順は保証されるのか