Avatar
0
Nguyễn Thái Sơn Professional
Nguyễn Thái Sơn Professional
set và arraylist trong Java
Anh ơi, Arraylist -> cho phép trùng phần tử còn Set k cho trùng phần tử, vậy bản chất Set cho phải là 1 arraylist, trước khi add vào nó check có phần tử trong list chưa, như vậy việc insert sẽ chậm hơn đúng k ạ vì bây giờ trong set có 1 tỷ phần tử, add phần tử 1 tỷ lẻ 1 vào thì nó phải quét 1 tỷ phần tử kia để check, số phần tử càng nhiều càng insert chậm
  • Answer
Remain: 5
1 Answer
Avatar
Vu Luong Anh Professional
Vu Luong Anh Professional
Set trong java được cài đặt bằng cấu trúc dữ liệu khác chứ không phải ArrayList. Ví dụ HashSet dùng Hash Table, nên insert chỉ mất O(1). Trong khi đó TreeSet dùng Red-black tree, insert mất O(log N).

ArrayList: Nếu insert ở cuối list thì mất O(1) trong hầu hết trường hợp (trừ khi số phần tử đạt đến giới hạn array thì phải tạo array mới, mất O(N)). Nếu insert vị trí bất kì thì mất O(N).

  • 2
  • Reply