Language/JAVA

[Java] LinkedHashMap์„ ํ†ตํ•œ ๊ธฐ์ดˆ ์บ์‹ฑ

PgmJUN 2024. 2. 25. 10:34

 

๐Ÿง ์บ์‹ฑ ๋ฐฉ์‹ ์‚ฌ์šฉ ์‹œ์— ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰์„ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ๋ฌด์—‡์ผ๊นŒ?

    @Test
    @DisplayName("๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰์„ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ๋ฌด์—‡์ผ๊นŒ?")
    void ๋ฉ”๋ชจ๋ฆฌ_์‚ฌ์šฉ๋Ÿ‰์„_์ตœ์†Œํ™”ํ•˜๋Š”_๋ฐฉ๋ฒ•์€_๋ฌด์—‡์ผ๊นŒ() {
        // TODO: ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰์„ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ๊ณ ๋ฏผ ํ›„ ๊ฐœ์„ ํ•ด๋ณด์„ธ์š”.
        record Position(int value) {
            private static final Map<Integer, Position> CACHE = new ConcurrentHashMap<>();

            public static Position startingPoint() {
                return valueOf(0);
            }

            public static Position valueOf(final int value) {
                return CACHE.computeIfAbsent(value, Position::new);
            }

 

์šฐํ…Œ์ฝ”์˜ ์ข‹์€ ์ฝ”๋“œ, ์ข‹์€ ์˜ˆ์™ธ ์ฒ˜๋ฆฌ ์ˆ˜์—…์—์„œ ์œ„์™€ ๊ฐ™์ด Map์„ ํ†ตํ•ด ๋ฐ์ดํ„ฐ๋ฅผ ์บ์‹ฑํ•˜๋Š” ์ƒํ™ฉ์—์„œ ๋ฉ”๋ชจ๋ฆฌ์˜ ์‚ฌ์šฉ๋Ÿ‰์„ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฐฉ๋ฒ•์ด ๋ฌด์—‡์ผ๊นŒ์— ๋Œ€ํ•œ ๋ฌธ์ œ๋ฅผ ๋ฐ›๊ฒŒ ๋˜์—ˆ๋‹ค.

 

 

์บ์‹ฑ์„ ํ•˜๊ฒŒ ๋œ ๋ฐฐ๊ฒฝ

record Position(int value) {
            Position() {
                this(0);
            }

            public Position increase() {
                return new Position(value + 1);
            }
        }

 

์šฐ์„  ์บ์‹ฑ์„ ํ•˜๋Š” ์ด์œ ๋Š” Position์„ ๋ถˆ๋ณ€์ƒํƒœ๋กœ ๋งŒ๋“ค์–ด์„œ ์˜ˆ์ธกํ•˜์ง€ ๋ชปํ•œ ๊ฐ’ ๋ณ€๋™์„ ๋ฐ”๊พธ๊ธฐ ์œ„ํ•ด ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ฝ”๋“œ๋ฅผ ์ฐจ์šฉํ–ˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

๋งค๋ฒˆ Position์ด ์ฆ๊ฐ€๋  ๋•Œ๋งˆ๋‹ค, ์‚ฌ์ด๋“œ ์ดํŽ™ํŠธ๋ฅผ ๋ฐฉ์ง€ํ•˜๊ธฐ ์œ„ํ•ด ์ƒˆ๋กœ์šด Position ๊ฐ์ฒด๋ฅผ ๋งŒ๋“ค์–ด์„œ returnํ•˜๊ณ  ์žˆ๋Š” ํ˜•ํƒœ์ด๋‹ค.

 

๋ฌผ๋ก  ๋ฌธ์ œ ํ•ด๊ฒฐ์—๋Š” ๋„์›€์ด ๋˜๊ฒ ์ง€๋งŒ ์ด๋ ‡๊ฒŒ ๊ด€๋ฆฌํ•˜๊ฒŒ ๋˜๋ฉด ๊ณ„์†ํ•ด์„œ Position ๊ฐ์ฒด๋ฅผ ์ƒ์„ฑํ•˜๊ฒŒ ๋˜๊ธฐ ๋•Œ๋ฌธ์— ์ด์— ๋Œ€ํ•œ ํ•ด๊ฒฐ์ฑ…์œผ๋กœ ์บ์‹ฑ์ด๋ผ๋Š” ๋ฐฉ๋ฒ•์„ ๋„์ž…ํ•˜๊ฒŒ ๋œ ์ƒํ™ฉ์ด๋‹ค.

 

 


 

๐Ÿ’ก LinkedHashMap์˜ removeEldestEntry

๋‚˜๋Š” ์ด ๋ฌธ์ œ์— ๋Œ€ํ•ด ๊ณ ๋ฏผํ•˜๋Š” ๊ณผ์ •์—์„œ LinkedHashMap์˜ removeEldestEntry() ๋ผ๋Š” ๋ฉ”์„œ๋“œ๋ฅผ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค.

 

LinkedHashMap์€ ์ €์žฅ๋œ ๋ฐ์ดํ„ฐ์˜ ์ˆœ์„œ๋ฅผ ๊ธฐ์–ตํ•˜๋Š” Map์ธ๋ฐ,

์ด๋Ÿฌํ•œ ํŠน์ง•์„ ์ด์šฉํ•˜์—ฌ Map์— ์„ค์ •ํ•œ ์ตœ๋Œ€ ์บ์‹ฑ ์ˆ˜๊ฐ€ N๊ฐœ๋ณด๋‹ค ๋งŽ์•„์กŒ์„ ์˜ค๋ž˜๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์‚ญ์ œํ•˜๋„๋ก ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ฉ”์„œ๋“œ์˜€๋‹ค.

 

๋‚˜๋Š” ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰ ์ตœ์†Œํ™”๋ผ๋Š” ์ฃผ์ œ์— ์ ์šฉํ•ด๋ณผ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ์‹ ์ค‘ ํ•˜๋‚˜๊ฐ€ ๋ฐ”๋กœ ์ด LinkedHashMap์ด๋ผ๊ณ  ์ƒ๊ฐ๋˜์–ด ๋ฐ”๋กœ ์ ์šฉํ•ด๋ณด์•˜๋‹ค.

 

 

    @Test
    @DisplayName("๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰์„ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ๋ฌด์—‡์ผ๊นŒ?")
    void ๋ฉ”๋ชจ๋ฆฌ_์‚ฌ์šฉ๋Ÿ‰์„_์ตœ์†Œํ™”ํ•˜๋Š”_๋ฐฉ๋ฒ•์€_๋ฌด์—‡์ผ๊นŒ() {
        // TODO: ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰์„ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ๊ณ ๋ฏผ ํ›„ ๊ฐœ์„ ํ•ด๋ณด์„ธ์š”.
        record Position(int value) {
            private static final Map<Integer, Position> CACHE = new LinkedHashMap<>() {
                static final int CACHE_MAX = 5;

                @Override
                protected boolean removeEldestEntry(Map.Entry<Integer, Position> eldest) {
                    return CACHE.size() >= CACHE_MAX;
                }
            };
            
            public static Position valueOf(final int value) {
                return CACHE.computeIfAbsent(value, Position::new);
            }
  • removeEldestEntry๋ฅผ Override ํ•˜์—ฌ CACHE_MAX๊ฐœ ์ด์ƒ์˜ ๋ฐ์ดํ„ฐ๊ฐ€ ์บ์‹ฑ๋˜๋ฉด, ์บ์‹ฑ๋œ์ง€ ์˜ค๋ž˜๋œ ์ˆœ์„œ๋Œ€๋กœ ๊ฐ’์„ ์‚ญ์ œํ•˜๋„๋ก ๋งŒ๋“ค์–ด์„œ CACHE_MAX ๋ณด๋‹ค ๋งŽ์€ ๋ฐ์ดํ„ฐ๊ฐ€ ์บ์‹ฑ๋˜์ง€ ์•Š๋„๋ก ์กฐ์ ˆํ•˜์˜€๋‹ค.

 

์ด ๋ฐฉ์‹์„ ํ™œ์šฉํ•˜๋ฉด ํ˜„์žฌ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋ฆฌ์†Œ์Šค์— ๋”ฐ๋ผ CACHE_MAX๋ฅผ ์ ์ ˆํ•˜๊ฒŒ ์กฐ์ ˆํ•˜์—ฌ ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰์„ ์ตœ์†Œํ™”ํ•  ์ˆ˜ ์žˆ๋„๋ก ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋‹ค.

 

๋ฌผ๋ก  ๋‹จ์ ์œผ๋กœ๋Š” ์ž์ฃผ ์‚ฌ์šฉ๋˜๋Š” ๊ฒƒ์„ ๊ตฌ๋ถ„ํ•˜๋Š” ๋ฐฉ์‹์ด ์•„๋‹Œ ์˜ค๋ž˜๋œ ์ˆœ์„œ๋Œ€๋กœ ์‚ญ์ œํ•œ๋‹ค๋Š” ์ ์ด ์žˆ๋‹ค.

๋•Œ๋ฌธ์— ์ž์ฃผ ์‚ฌ์šฉ๋˜๋Š” ๊ฒƒ์„ ๊ตฌ๋ถ„ํ•ด์„œ ์บ์‹ฑํ•ด์•ผํ•˜๋Š” ์ƒํ™ฉ์ด๋ผ๋ฉด ์ด ๋ฐฉ๋ฒ•์„ ์„ ํƒํ•˜๋Š” ๊ฒƒ์ด ๊ทธ๋ ‡๊ฒŒ ํšจ์œจ์ ์ด์ง„ ์•Š์„ ์ˆ˜๋„ ์žˆ๋‹ค.

 

 

์ ์šฉ ๊ฒฐ๊ณผ

 

์œ„ ๋ฐฉ์‹์„ ์ ์šฉํ•˜๊ณ  ๋‚˜๋‹ˆ, ์œ„์™€ ๊ฐ™์ด ์บ์‹ฑ ์‚ฌ์ด์ฆˆ๊ฐ€ CACHE_MAX ๋ฅผ ๋„˜์–ด๊ฐ€๋ฉด ์˜ค๋ž˜๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์ œ๊ฑฐํ•˜๋„๋ก ๋™์ž‘ํ•˜๋Š” ๊ฒƒ์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.

 

 

๋ฌธ์ œ์ 

์บ์‹œ์˜ ์ตœ๋Œ€ ํ•œ๊ณ„์น˜๋ฅผ ์„ค์ •ํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ์ ์€ ์•Œ๊ฒ ๋Š”๋ฐ, ์ž์ฃผ ์‚ฌ์šฉ๋˜๋Š” ๊ฒƒ์„ ๊ตฌ๋ถ„ํ•˜๋Š” ๋ฐฉ์‹์ด ์•„๋‹ˆ๋ผ Insert๋œ ์ง€ ์˜ค๋ž˜๋œ ์ˆœ์„œ๋Œ€๋กœ ์‚ญ์ œํ•œ๋‹ค๋Š” ํฐ ๋ฌธ์ œ์ ์€ ์–ด๋–ป๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์„๊นŒ?

 

์ด์— ๋Œ€ํ•œ ํ•ด๊ฒฐ์ฑ…์œผ๋กœ LinkedHashMap์ด ์ œ๊ณตํ•˜๋Š” Ordering Mode ์ค‘ Access-Order ๋ฐฉ์‹ ์„ ํ™œ์šฉํ•ด ๋ณผ ์ˆ˜ ์žˆ๊ฒ ๋‹ค.

 

 


 

๐Ÿ’ก LinkedHashMap์˜ Ordering Mode

 

LinkedHashMap์€ Ordering Mode๋ผ๋Š” ๊ฒƒ์„ ํ†ตํ•ด ์˜ค๋ž˜๋œ ๋ฐ์ดํ„ฐ๋ฅผ ํŒ๋‹จํ•˜๋Š” ๊ธฐ์ค€์„ 2๊ฐ€์ง€ ๊ธฐ์ค€์œผ๋กœ ๊ตฌ๋ถ„ํ•  ์ˆ˜ ์žˆ๋‹ค.

 

Insertion-Order (์‚ฝ์ž… ๊ธฐ์ค€ ์ •๋ ฌ)

  • Insertion-Order๋ž€ ๋ฐ์ดํ„ฐ๊ฐ€ Insert ๋œ ์ˆœ์„œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค.
  • LHM์„ ๊ธฐ๋ณธ ์ƒ์„ฑ์ž๋กœ ์ƒ์„ฑํ•˜๊ฒŒ ๋˜๋ฉด Ordering Mode ์„ค์ •์„ ๋‹ด๋‹นํ•˜๋Š” accessOrder๊ฐ€ false๋กœ ์„ค์ •๋˜์–ด ์ž๋™์œผ๋กœ Insertion-order ๋ชจ๋“œ๋กœ ์„ค์ •๋œ๋‹ค.

 

Access-Order (์ ‘๊ทผ ๊ธฐ์ค€ ์ •๋ ฌ)

  • Access-Order ๋ž€ ๋ฐ์ดํ„ฐ๊ฐ€ ์ตœ๊ทผ ์ ‘๊ทผ๋œ ์ˆœ์„œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค.
  • LHM์ด ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉํ•˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ ๊ต์ฒดํ•˜๋Š” ๊ธฐ๋ฒ•์ธ LRU(Least Recently Used) ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋„๋ก ์ œ๊ณตํ•˜๋Š” ๊ธฐ๋Šฅ์ด๋‹ค.
  • initialCapacity, loadFactor, accessOrder๋ฅผ ์ž…๋ ฅ๋ฐ›๋Š” ์ƒ์„ฑ์ž๋ฅผ ํ†ตํ•ด ์‚ฌ์šฉ ๊ฐ€๋Šฅํ•˜๋‹ค.

 

๐Ÿ”‘ initialCapacity

  • ์ดˆ๊ธฐ Map์˜ ์šฉ๋Ÿ‰์— ๋Œ€ํ•œ ๊ฐ’์ด๋‹ค.
  • ๊ธฐ๋ณธ ์ƒ์„ฑ์ž์˜ Default ๊ฐ’์€ 16์ด๋‹ค.

๐Ÿ”‘ loadFactor

  • Map์˜ ์šฉ๋Ÿ‰์ด ์–ด๋Š์ •๋„ ์ฐผ์„ ๋•Œ capacity๋ฅผ ํ™•์žฅํ•  ์ง€์— ๋Œ€ํ•œ ๊ฐ’์ด๋‹ค.
  • ๊ธฐ๋ณธ ์ƒ์„ฑ์ž์˜ Default ๊ฐ’์€ 0.75f์ด๋‹ค.

๐Ÿ”‘ accessOrder

  • Ordering Mode ์„ค์ •์„ ๋‹ด๋‹นํ•˜๋Š” ๊ฐ’์œผ๋กœ true๋กœ ์„ ํƒ ์‹œ, Access-Order ๋ชจ๋“œ๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

 

 


 

๐Ÿ’ก Access-Order ๋ชจ๋“œ ์ ์šฉ

 

record Position(int value) {
    private static final Map<Integer, Position> CACHE = new LinkedHashMap<>(16, 0.75f, true) {
        static final int CACHE_MAX = 5;

        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Position> eldest) {
            System.out.println(CACHE);
            return CACHE.size() >= CACHE_MAX;
        }
    };
  • LHM์„ Access-Order ๋ชจ๋“œ ์ ์šฉ์„ ํ†ตํ•ด ์ตœ๊ทผ์— ์ ‘๊ทผํ•œ ์ˆœ์„œ๋Œ€๋กœ Map์˜ ์š”์†Œ๋“ค์„ ์ •๋ ฌํ•˜์—ฌ,
    ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์กฐํšŒ๋˜์ง€ ์•Š์€ ๊ฐ’์„ ์˜ค๋ž˜๋˜์—ˆ๋‹ค๊ณ  ํŒ๋‹จํ•˜๋„๋ก ์„ค์ •
  • ์ด๋ฅผ ํ†ตํ•ด ์‚ฌ์šฉ๋˜์ง€ ์•Š๋Š” ๊ฐ’๋“ค์€ ์ž์—ฐ์Šค๋ ˆ ์บ์‹œ ๋ฉ”๋ชจ๋ฆฌ์—์„œ ์ œ๊ฑฐํ•˜๊ณ  ์ž์ฃผ ์‚ฌ์šฉ๋˜๋Š” ๊ฐ’๋“ค์€ ์˜ค๋žซ๋™์•ˆ ์œ ์ง€

 

์ ์šฉ ๊ฒฐ๊ณผ

 

์œ„ ์ฝ”๋“œ ์ ์šฉ์„ ํ†ตํ•ด ์‚ฌ์ง„ ๋งˆ์ง€๋ง‰ ์ค„์—์„œ ๋ณผ ์ˆ˜ ์žˆ๋“ฏ์ด 1,2,3,4,5๋ฅผ ์ˆœ์ฐจ์ ์œผ๋กœ ์ƒ์„ฑํ•œ ํ›„, 1๋ฒˆ์— ์ ‘๊ทผ ํ•˜์˜€์„ ๋•Œ

๋งจ ๋’ค์— ์žˆ๋˜ 1๋ฒˆ์ด ๊ฐ€์žฅ ๋งจ ์•ž์œผ๋กœ ์˜ค๋Š” ๊ฒƒ์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.

 

 


 

๋งˆ๋ฌด๋ฆฌ

2์ฃผ๊ฐ„ ์šฐํ…Œ์ฝ”์—์„œ ํ•™์Šตํ•˜๋ฉฐ ๋Š๋‚€ ์šฐํ…Œ์ฝ”์˜ ์žฅ์ ์€

์ข‹์€ ์ฝ”๋“œ๋ฅผ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด ๋” ๊นŠ์ด ์žˆ๊ฒŒ ํ•™์Šตํ•˜๊ณ , ๋” ๊นŠ์ด์žˆ๊ฒŒ ๊ณ ๋ฏผํ•  ์ˆ˜ ์žˆ๋Š” ํ™˜๊ฒฝ์„ ์กฐ์„ฑํ•ด์ค€๋‹ค๋Š” ์ ์ธ ๊ฒƒ ๊ฐ™๋‹ค.

 

์šฐํ…Œ์ฝ”์—์„œ ์ฒด๊ณ„์ ์ธ ๋ฏธ์…˜๊ณผ ์ˆ˜์—… ๊ทธ๋ฆฌ๊ณ  ์ˆ˜์ค€ ๋†’์€ ๋ฆฌ๋ทฐ๋ฅผ ๋ฐ›์•„๋ณด๋ฉฐ ๋‚ด๊ฐ€ ๋ถ€์กฑํ•œ ๊ฒƒ์ด ๋ฌด์—‡์ธ์ง€์— ๋Œ€ํ•ด ์ง๊ด€์ ์œผ๋กœ ํŒŒ์•…ํ•  ์ˆ˜ ์žˆ๊ฒŒ ๋˜์—ˆ๊ณ ,
ํŽ˜์–ด ํ”„๋กœ๊ทธ๋ž˜๋ฐ์„ ํ†ตํ•ด ํŽ˜์–ด์™€ ์ฝ”๋“œ์— ๋Œ€ํ•œ ๊ณ ๋ฏผ์„ ์ƒ๊ฐ์ด ์•„๋‹Œ ๋Œ€ํ™”๋กœ ์ฃผ๊ณ  ๋ฐ›์œผ๋ฉด์„œ ๋จธ๋ฆฟ์†์— ์–ด์งˆ๋Ÿฌ์ ธ์žˆ๋˜ ์ƒ๊ฐ๊ณผ ๊ฐœ๋…๋“ค์ด ๊ฐ€์ง€๋Ÿฐํžˆ ์ •๋ฆฌ๋˜์–ด ๊ฐ„๋‹ค๋Š” ๊ฒƒ์„ ๋Š๊ผˆ๋‹ค.

๋˜, ํŽ˜์–ด ๋ฟ๋งŒ ์•„๋‹ˆ๋ผ ํฌ๋ฃจ์›๋“ค๊ณผ ๋Œ€ํ™”ํ•˜๋Š” ๊ณผ์ •์—์„œ๋„ ๋งŽ์€ ์ธ์‚ฌ์ดํŠธ์™€ ๋™๊ธฐ๋ถ€์—ฌ๋ฅผ ์–ป๊ณ  ์žˆ๋Š” ์š”์ฆ˜์ด๋‹ค.

ํฌ์ŠคํŒ…์˜ ๋‚ด์šฉ ๋˜ํ•œ ํฌ๋ฃจ์›๋“ค๊ณผ ๋Œ€ํ™” ์ค‘ WeakHashMap ์ด๋ผ๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋˜์–ด, ์ด์— ๋Œ€ํ•ด ํ•™์Šตํ•˜๋Š” ๊ณผ์ •์—์„œ ์ƒˆ๋กญ๊ฒŒ ๋ฐฐ์šด ๋‚ด์šฉ์ด๋‹ค.

 

์—ญ์‹œ ๊ฐœ๋ฐœ์€ ํ˜ผ์ž๊ฐ€ ์•„๋‹Œ ํ•จ๊ป˜ํ•  ๋•Œ ๊ฐ€์žฅ ๋น ๋ฅด๊ฒŒ ์„ฑ์žฅํ•ด๋‚˜๊ฐ€๋Š” ๊ฒƒ ๊ฐ™๋‹ค๐Ÿ”ฅ

 

 


 

Reference

https://camel-context.tistory.com/42

728x90
๋ฐ˜์‘ํ˜•