diff --git a/framework-t/src/android/net/NetworkStatsHistory.java b/framework-t/src/android/net/NetworkStatsHistory.java
index 0ff9d96..738e9cc 100644
--- a/framework-t/src/android/net/NetworkStatsHistory.java
+++ b/framework-t/src/android/net/NetworkStatsHistory.java
@@ -58,6 +58,7 @@
 import java.util.Arrays;
 import java.util.List;
 import java.util.Random;
+import java.util.TreeMap;
 
 /**
  * Collection of historical network statistics, recorded into equally-sized
@@ -253,6 +254,28 @@
                     + ", operations=" + operations
                     + "}";
         }
+
+        /**
+         * Add the given {@link Entry} with this instance and return a new {@link Entry}
+         * instance as the result.
+         *
+         * @hide
+         */
+        @NonNull
+        public Entry plus(@NonNull Entry another, long bucketDuration) {
+            if (this.bucketStart != another.bucketStart) {
+                throw new IllegalArgumentException("bucketStart " + this.bucketStart
+                        + " is not equal to " + another.bucketStart);
+            }
+            return new Entry(this.bucketStart,
+                    // Active time should not go over bucket duration.
+                    Math.min(this.activeTime + another.activeTime, bucketDuration),
+                    this.rxBytes + another.rxBytes,
+                    this.rxPackets + another.rxPackets,
+                    this.txBytes + another.txBytes,
+                    this.txPackets + another.txPackets,
+                    this.operations + another.operations);
+        }
     }
 
     /** @hide */
@@ -1109,14 +1132,8 @@
      * Builder class for {@link NetworkStatsHistory}.
      */
     public static final class Builder {
+        private final TreeMap<Long, Entry> mEntries;
         private final long mBucketDuration;
-        private final List<Long> mBucketStart;
-        private final List<Long> mActiveTime;
-        private final List<Long> mRxBytes;
-        private final List<Long> mRxPackets;
-        private final List<Long> mTxBytes;
-        private final List<Long> mTxPackets;
-        private final List<Long> mOperations;
 
         /**
          * Creates a new Builder with given bucket duration and initial capacity to construct
@@ -1127,66 +1144,31 @@
          */
         public Builder(long bucketDuration, int initialCapacity) {
             mBucketDuration = bucketDuration;
-            mBucketStart = new ArrayList<>(initialCapacity);
-            mActiveTime = new ArrayList<>(initialCapacity);
-            mRxBytes = new ArrayList<>(initialCapacity);
-            mRxPackets = new ArrayList<>(initialCapacity);
-            mTxBytes = new ArrayList<>(initialCapacity);
-            mTxPackets = new ArrayList<>(initialCapacity);
-            mOperations = new ArrayList<>(initialCapacity);
-        }
-
-        private void addToElement(List<Long> list, int pos, long value) {
-            list.set(pos, list.get(pos) + value);
+            // Create a collection that is always sorted and can deduplicate items by the timestamp.
+            mEntries = new TreeMap<>();
         }
 
         /**
-         * Add an {@link Entry} into the {@link NetworkStatsHistory} instance.
+         * Add an {@link Entry} into the {@link NetworkStatsHistory} instance. If the timestamp
+         * already exists, the given {@link Entry} will be combined into existing entry.
          *
-         * @param entry The target {@link Entry} object. The entry timestamp must be greater than
-         *              that of any previously-added entry.
+         * @param entry The target {@link Entry} object.
          * @return The builder object.
          */
         @NonNull
         public Builder addEntry(@NonNull Entry entry) {
-            final int lastBucket = mBucketStart.size() - 1;
-            final long lastBucketStart = (lastBucket != -1) ? mBucketStart.get(lastBucket) : 0;
-
-            // If last bucket has the same timestamp, modify it instead of adding another bucket.
-            // This allows callers to pass in the same bucket twice (e.g., to accumulate
-            // data over time), but still requires that entries must be sorted.
-            // The importer will do this in case a rotated file has the same timestamp as
-            // the previous file.
-            if (lastBucket != -1 && entry.bucketStart == lastBucketStart) {
-                addToElement(mActiveTime, lastBucket, entry.activeTime);
-                addToElement(mRxBytes, lastBucket, entry.rxBytes);
-                addToElement(mRxPackets, lastBucket, entry.rxPackets);
-                addToElement(mTxBytes, lastBucket, entry.txBytes);
-                addToElement(mTxPackets, lastBucket, entry.txPackets);
-                addToElement(mOperations, lastBucket, entry.operations);
-                return this;
+            final Entry existing = mEntries.get(entry.bucketStart);
+            if (existing != null) {
+                mEntries.put(entry.bucketStart, existing.plus(entry, mBucketDuration));
+            } else {
+                mEntries.put(entry.bucketStart, entry);
             }
-
-            // Inserting in the middle is prohibited for performance reasons.
-            if (entry.bucketStart <= lastBucketStart) {
-                throw new IllegalArgumentException("new bucket start " + entry.bucketStart
-                        + " must be greater than last bucket start " + lastBucketStart);
-            }
-
-            // Common case: add entries at the end of the list.
-            mBucketStart.add(entry.bucketStart);
-            mActiveTime.add(entry.activeTime);
-            mRxBytes.add(entry.rxBytes);
-            mRxPackets.add(entry.rxPackets);
-            mTxBytes.add(entry.txBytes);
-            mTxPackets.add(entry.txPackets);
-            mOperations.add(entry.operations);
             return this;
         }
 
-        private static long sum(@NonNull List<Long> list) {
-            long sum = 0;
-            for (long entry : list) {
+        private static long sum(@NonNull long[] array) {
+            long sum = 0L;
+            for (long entry : array) {
                 sum += entry;
             }
             return sum;
@@ -1199,16 +1181,30 @@
          */
         @NonNull
         public NetworkStatsHistory build() {
-            return new NetworkStatsHistory(mBucketDuration,
-                    CollectionUtils.toLongArray(mBucketStart),
-                    CollectionUtils.toLongArray(mActiveTime),
-                    CollectionUtils.toLongArray(mRxBytes),
-                    CollectionUtils.toLongArray(mRxPackets),
-                    CollectionUtils.toLongArray(mTxBytes),
-                    CollectionUtils.toLongArray(mTxPackets),
-                    CollectionUtils.toLongArray(mOperations),
-                    mBucketStart.size(),
-                    sum(mRxBytes) + sum(mTxBytes));
+            int size = mEntries.size();
+            final long[] bucketStart = new long[size];
+            final long[] activeTime = new long[size];
+            final long[] rxBytes = new long[size];
+            final long[] rxPackets = new long[size];
+            final long[] txBytes = new long[size];
+            final long[] txPackets = new long[size];
+            final long[] operations = new long[size];
+
+            int i = 0;
+            for (Entry entry : mEntries.values()) {
+                bucketStart[i] = entry.bucketStart;
+                activeTime[i] = entry.activeTime;
+                rxBytes[i] = entry.rxBytes;
+                rxPackets[i] = entry.rxPackets;
+                txBytes[i] = entry.txBytes;
+                txPackets[i] = entry.txPackets;
+                operations[i] = entry.operations;
+                i++;
+            }
+
+            return new NetworkStatsHistory(mBucketDuration, bucketStart, activeTime,
+                    rxBytes, rxPackets, txBytes, txPackets, operations,
+                    size, sum(rxBytes) + sum(txBytes));
         }
     }
 }
diff --git a/tests/common/java/android/net/netstats/NetworkStatsHistoryTest.kt b/tests/common/java/android/net/netstats/NetworkStatsHistoryTest.kt
index f8e041a..a6c9f3c 100644
--- a/tests/common/java/android/net/netstats/NetworkStatsHistoryTest.kt
+++ b/tests/common/java/android/net/netstats/NetworkStatsHistoryTest.kt
@@ -27,7 +27,6 @@
 import org.junit.runner.RunWith
 import org.junit.runners.JUnit4
 import kotlin.test.assertEquals
-import kotlin.test.assertFailsWith
 
 @ConnectivityModuleTest
 @RunWith(JUnit4::class)
@@ -53,21 +52,36 @@
         statsSingle.assertEntriesEqual(entry1)
         assertEquals(DateUtils.HOUR_IN_MILLIS, statsSingle.bucketDuration)
 
-        // Verify the builder throws if the timestamp of added entry is not greater than
-        // that of any previously-added entry.
-        assertFailsWith(IllegalArgumentException::class) {
-            NetworkStatsHistory
-                    .Builder(DateUtils.SECOND_IN_MILLIS, /* initialCapacity */ 0)
-                    .addEntry(entry1).addEntry(entry2).addEntry(entry3)
-                    .build()
-        }
+        val statsMultiple = NetworkStatsHistory
+                .Builder(DateUtils.SECOND_IN_MILLIS, /* initialCapacity */ 0)
+                .addEntry(entry1).addEntry(entry2).addEntry(entry3)
+                .build()
+        assertEquals(DateUtils.SECOND_IN_MILLIS, statsMultiple.bucketDuration)
+        // Verify the entries exist and sorted.
+        statsMultiple.assertEntriesEqual(entry3, entry1, entry2)
+    }
+
+    @Test
+    fun testBuilderSortAndDeduplicate() {
+        val entry1 = NetworkStatsHistory.Entry(10, 30, 40, 4, 50, 5, 60)
+        val entry2 = NetworkStatsHistory.Entry(30, 15, 3, 41, 7, 1, 0)
+        val entry3 = NetworkStatsHistory.Entry(30, 999, 11, 14, 31, 2, 80)
+        val entry4 = NetworkStatsHistory.Entry(10, 15, 1, 17, 5, 33, 10)
+        val entry5 = NetworkStatsHistory.Entry(6, 1, 9, 11, 29, 1, 7)
+
+        // Entries for verification.
+        // Note that active time of 2 + 3 is truncated to bucket duration since the active time
+        // should not go over bucket duration.
+        val entry2and3 = NetworkStatsHistory.Entry(30, 1000, 14, 55, 38, 3, 80)
+        val entry1and4 = NetworkStatsHistory.Entry(10, 45, 41, 21, 55, 38, 70)
 
         val statsMultiple = NetworkStatsHistory
                 .Builder(DateUtils.SECOND_IN_MILLIS, /* initialCapacity */ 0)
-                .addEntry(entry3).addEntry(entry1).addEntry(entry2)
-                .build()
+                .addEntry(entry1).addEntry(entry2).addEntry(entry3)
+                .addEntry(entry4).addEntry(entry5).build()
         assertEquals(DateUtils.SECOND_IN_MILLIS, statsMultiple.bucketDuration)
-        statsMultiple.assertEntriesEqual(entry3, entry1, entry2)
+        // Verify the entries sorted and deduplicated.
+        statsMultiple.assertEntriesEqual(entry5, entry1and4, entry2and3)
     }
 
     fun NetworkStatsHistory.assertEntriesEqual(vararg entries: NetworkStatsHistory.Entry) {